CSP2020-j2 T4 方格取数

题目链接：https://www.luogu.com.cn/problem/P7074

一、dfs(25分)没有任何优化，时间复杂度约（O（3^(n*m)））

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 int a[1005][1005], vis[1005][1005];
 5 int nex[3][2]={{-1,0},{1,0},{0,1}};
 6 int sum;
 7 int ans=-0x7fffffff;
 8 void dfs(int x, int y){
 9     if(x==1 && y==1){
10         vis[x][y]=1;
11         sum=a[x][y];
12     }
13     if(x==n && y==m){
14         ans=max(ans, sum);
15         return;
16     }
17     for(int i=0; i<3; i++){
18         int nx=x+nex[i][0], ny=y+nex[i][1];
19         if(nx<1 || nx>n || ny<1 || ny>m)continue;
20         if(vis[nx][ny])continue;
21         vis[nx][ny]=1;
22         sum+=a[nx][ny];
23         dfs(nx, ny);
24         sum-=a[nx][ny];
25         vis[nx][ny]=0;
26     }
27 }
28 int main()
29 {
30     cin>>n>>m;
31     for(int i=1; i<=n; i++)
32         for(int j=1; j<=m; j++)
33             cin>>a[i][j];                
34     dfs(1,1);
35     cout<<ans;
36     return 0;
37  }