求助记忆化搜索 10 pts
查看原帖
求助记忆化搜索 10 pts
574944
Micnation_AFO楼主2022/8/5 22:08
#include <iostream>

using namespace std;

const int N = 1e3 + 10;
const int INF = 1e7;

int n, m;
int a[N][N];
int f[N][N];
bool vis[N][N];

int dfs(int x, int y) {
    if (x > n || y > m || x <= 0 || y <= 0) return -INF;
    if (f[x][y] != -INF) return f[x][y];
    if (x == 1 && y == 1) return f[x][y] = a[x][y];
    vis[x][y] = true;
    if (!vis[x - 1][y]) f[x][y] = max(f[x][y], dfs(x - 1, y) + a[x][y]);
    if (!vis[x + 1][y]) f[x][y] = max(f[x][y], dfs(x + 1, y) + a[x][y]);
    if (!vis[x][y - 1]) f[x][y] = max(f[x][y], dfs(x, y - 1) + a[x][y]);
    vis[x][y] = false;
    return f[x][y];
} 

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++) f[i][j] = -INF;
    cout << dfs(n, m);
    return 0;
}
2022/8/5 22:08
加载中...