n行m列的网格,从(1, 1)走到(n, m)
每到一个格点,加上格点的数值,求到终点时的最大数值。
只能往上、下、右三个方向走,当从上/下边界越界时,从地图对应的另一边出现,且累计数值清零。
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 110, INF = 1e9;
int n, m;
int s[N][N], f[N][N];
bool st[N][N];
int res;
int dx[]= {0, 1, -1}, dy[] = {1, 0, 0}; // 只能往上、下、右三个方向走
void dfs(int x, int y)
{
if (x == n && y == m)
{
res = max(res, f[x][y]);
return;
}
for (int i = 0; i < 3; i ++)
{
int a = x + dx[i], b = y + dy[i];
if (b > m) continue;
if (a == 0) // 从上边界越界,出现在地图对应的另一边
{
a = n;
if (st[a][b]) continue;
f[a][b] = s[a][b];
}
else if (a == n + 1) // 从下边界越界,出现在地图对应的另一边
{
a = 1;
if (st[a][b]) continue;
f[a][b] = s[a][b];
}
else
{
if (st[a][b]) continue;
f[a][b] = f[x][y] + s[a][b];
}
st[a][b] = true;
dfs(a, b);
st[a][b] = false; // 恢复现场
}
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
cin >> s[i][j];
f[i][j] = -INF; // 初始化累计值为负极大值
}
st[1][1] = true;
f[1][1] = s[1][1];
dfs(1, 1);
cout << res;
return 0;
}