洛谷 P1123 取数游戏_

洛谷 P1123 取数游戏__（刷题)bfs

题目：https://www.luogu.org/problemnew/show/P1123

稍微需要一些剪枝的dfs，否则只有50分；

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int xx[9]={0,0,0,1,1,1,-1,-1,-1};
 5 int yy[9]={1,0,-1,1,0,-1,1,0,-1};
 6 int ans=0;
 7 int a[20][20];
 8 int used[20][20];
 9 int n,m,t;
10 
11 void dfs(int x,int y,int sum)
12 {
13     if(x>n)
14     {
15         ans = max(ans,sum);
16         return ;
17     }
18     int dx=x,dy=y+1;
19     if(dy>m)
20     {
21         dx++;
22         dy=1;
23     }
24     if(!used[x][y])
25     {
26         for(int i=0;i<9;i++) used[x+xx[i]][y+yy[i]]++;
27         dfs(dx,dy,sum+a[x][y]);
28         for(int i=0;i<9;i++) used[x+xx[i]][y+yy[i]]--;
29     }
30     dfs(dx,dy,sum);
31 }
32 int main()
33 {
34     scanf("%d",&t);
35     while(t--)
36     {
37         memset(used,0,sizeof(used));
38         cin>>n>>m;
39         for(int i=1;i<=n;i++)
40             for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
41         dfs(1,1,0);
42         printf("%d
",ans);
43         memset(used,0,sizeof(used));
44         ans=0;
45     }
46 
47 }

我的思路是：一行一行的搜索；

找到一种，将就把他和他周围的8个全部标记掉；

注意！！初始化！！