洛谷原题
题目描述
设有 n×m 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。
输入格式
第一行有两个整数 n,m。
接下来 n 行每行 m 个整数，依次代表每个方格中的整数。
输出格式
一个整数，表示小熊能取到的整数之和的最大值。
#include <bits/stdc++.h>
using namespace std;
long long a[1005][1005][3],b[1005][1005],n,m,max_;
int dfs(int x,int y,int sx) {//上为1，下为2，左为0
if(a[x][y][sx]||(x==1&&y==1))return a[x][y][sx];
if(x>n||x<1||y>m||y<1) return -1e9;
if(sx==1)a[x][y][sx]=b[x][y]+max(dfs(x-1,y,1),dfs(x-1,y,0));
else if(sx==2)a[x][y][sx]=b[x][y]+max(dfs(x+1,y,2),dfs(x+1,y,0));
else a[x][y][sx]=b[x][y]+max(dfs(x,y-1,1),max(dfs(x,y-1,2),dfs(x,y-1,0)));
return a[x][y][sx];
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
cin>>b[i][j];
a[1][1][0]=a[1][1][1]=a[1][1][2]=b[1][1];
cout<<max(max(dfs(n,m,0),dfs(n,m,1)),dfs(n,m,2))<<endl;
return 0;
}
嘉仁们，帮亥仔看一下哪里错了吧……邱邱了……
