我先写了个暴力试一下水......淹死了
哪错了啊?
#include<iostream>
using namespace std;
int mi=0-0x7fffffff;
int n,m;
int a[1001][1001],c[1001][1001];
int x1[3]={1,0,-1},y1[3]={0,1,0};//上下右
void dfs(int x,int y,int z)
{
if(x==n&&y==m)
{
mi=max(mi,z);
return ;
}
for(int i=0;i<3;i++)//穷尽路线
{
int t1=x+x1[i];
int t2=y+y1[i];
if(t1<=0||t1>n||t2>m||c[t1][t2])
continue;
c[t1][t2]=1;//标记,防回路
dfs(t1,t2,z+a[t1][t2]);
c[t1][t2]=0;//回溯
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int u=1;u<=m;u++)
cin>>a[i][u];
dfs(1,1,a[1][1]);
cout<<mi;//最大值
return 0;
}
/*
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
9
5 5
7 0 4 8 -4
5 7 1 2 6
4 3 -2 6 5
-6 8 2 9 4
1 3 -4 -1 8
81
*/