60pts求调(玄关)
查看原帖
60pts求调(玄关)
1346030
封禁用户楼主2024/7/16 15:53
#include <bits/stdc++.h>
#define N 101
#define ll long long
using namespace std;

int n, m;
int dp[N][N], dp1[N][N], a[N][N], xx[5] = {0, 1, 0, -1, 0}, yy[5] = {0, 0, 1, 0, -1};
bool b[N][N];

inline void dfs(int x, int y, bool g) {
    if (x == 1 && y == 1 && g == 1)
        return;
    if (x == n && y == m && g == 0) {
        g = 1;
        dp1[n][m] = dp[n][m];
    }
    int u, v;
    if (g == 0) {
        for (int i = 1; i <= 2; i++) {
            u = x + xx[i];
            v = y + yy[i];
            if (u >= 1 && u <= n && v >= 1 && v <= m) {
                if (b[u][v] == 0) {
                    if (dp[u][v] < dp[x][y] + a[u][v]) {
                        dp[u][v] = dp[x][y] + a[u][v];
                        b[u][v] = 1;
                        dfs(u, v, g);
                        b[u][v] = 0;
                    }
                }
            }
        }
    } else {
        if (g == 1) {
            for (int i = 3; i <= 4; i++) {
                u = x + xx[i];
                v = y + yy[i];
                if (u >= 1 && u <= n && v >= 1 && v <= m) {
                    if (b[u][v] == 0) {
                        if (dp1[u][v] < dp1[x][y] + a[u][v]) {
                            dp1[u][v] = dp1[x][y] + a[u][v];
                            b[u][v] = 1;
                            dfs(u, v, g);
                            b[u][v] = 0;
                        }
                    }
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    memset(b, false, sizeof(b));
    dfs(1, 1, false);
    printf("%d", dp1[1][1]);
}
2024/7/16 15:53
加载中...