洛谷1123 取数游戏

  • 对于所有要大暴搜的$dfs$,一定要把能剪得枝都剪了,不然很容易爆空间、爆时间。
  • 直接大暴搜即可,只要在选点的时候进行判断是否合法即可。
  • Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,data[20][20],ans,T;
bool book[20][20];
bool check(int x,int y){
if (!book[x][y+1]&&!book[x][y-1]&&!book[x+1][y]&&!book[x+1][y+1]&&!book[x+1][y-1]&&!book[x-1][y]&&!book[x-1][y+1]&&!book[x-1][y-1])
return true;
return false;
}
void dfs(int x,int y,int sum){
ans=max(ans,sum);
int ty=y+1,tx=x;
if(ty>m){
tx=x+1;
ty=1;
if(tx>n) return;
}
if(check(tx,ty)){
book[tx][ty]=true;
dfs(tx,ty,sum+data[tx][ty]);//选这个点
book[tx][ty]=false;
}
dfs(tx,ty,sum);//不选这个点
return;
}
int main(){
scanf("%d",&T);
while(T--){
ans=0;
memset(book,0,sizeof(book));//初始化
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>data[i][j];
book[1][1]=true;
dfs(1,1,data[1][1]);//注意第一个点也要考虑!
book[1][1]=false;
dfs(1,1,0);
printf("%d\n",ans);
}
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×