深度优先搜索算法（3）——习题简述（2）

本节将给出以下题的题解：

1. P1123 取数游戏
2. P1605 迷宫
3. P1644 跳马问题
4. P1219 八皇后

代码仓库链接：https://github.com/zhenghan123456/algotithm_programming

在这里建议每道题都认真思考，习题题解只是简单表明一下思路，不会和例题一样具体

2.3.5P1123 取数游戏

这道题是一道没那么明显的DFS题，这就不是简单通过状压就可以解决的（因为剪枝可以减掉很多情况来优化效率），对于每一个点，都有选和不选两种情况，然后检验是否满足情况就可以了。

这个选数问题最难的地方在于考虑到DFS的使用，而不是具体实现，应该熟记题目代码模板

代码位置：2\problems\P1123.cpp

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'intn,m;boolvis[8][8];intdx[]={1,1,1,-1,-1,-1,0,0};intdy[]={1,-1,0,1,-1,0,1,-1};inta[8][8];intans=0;voiddfs(intx,inty,intsum){// 全部格子遍历完成，更新答案if(x>=n){ans=max(ans,sum);return;}// 计算下一个坐标：本行没结束就y+1；否则下一行开头intnx,ny;if(y+1<m){nx=x;ny=y+1;}else{nx=x+1;ny=0;}// 不选dfs(nx,ny,sum);// 选boolok=1;_for(i,8){inttx=x+dx[i];intty=y+dy[i];if(tx>=0&&tx<n&&ty>=0&&ty<m&&vis[tx][ty]){ok=0;break;}}if(ok){vis[x][y]=1;dfs(nx,ny,sum+a[x][y]);vis[x][y]=0;}}intmain(){ios::sync_with_stdio(0);cin.tie(0);int_;cin>>_;while(_--){cin>>n>>m;_for(i,n)_for(j,m)cin>>a[i][j];ans=0;memset(vis,0,sizeof(vis));dfs(0,0,0);cout<<ans<<endl;}return0;}

2.3.6P1605 迷宫

迷宫DFS模板题，适当掌握技巧即可

代码位置：2\problems\P1605.cpp

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'intsx,sy,fx,fy;intn,m,t;boolmatrix[5][5];boolvis[5][5];intdx[]={1,0,-1,0};// 方向数组intdy[]={0,1,0,-1};intdfs(intx,inty){if(x==fx&&y==fy)return1;// 到终点了intcnt=0;_for(i,4){// 越界检查if((x+dx[i]<0)||(y+dy[i]<0))continue;if((x+dx[i]>=n)||(y+dy[i]>=m))continue;if(!matrix[x+dx[i]][y+dy[i]]&&(!vis[x+dx[i]][y+dy[i]])){vis[x+dx[i]][y+dy[i]]=true;// 添加标记cnt+=dfs(x+dx[i],y+dy[i]);vis[x+dx[i]][y+dy[i]]=false;// 撤销标记}}returncnt;// 既然没有到达终点的可能（已经排除了）那么遇到死胡同直接返回0即可无需判断}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m>>t;cin>>sx>>sy>>fx>>fy;sx--;sy--;fx--;fy--;vis[sx][sy]=true;// 先给起点打上标记while(t--){intx,y;cin>>x>>y;x--;y--;matrix[x][y]=true;}cout<<dfs(sx,sy)<<endl;}

2.4.7P1644 跳马问题

相当于是一道寻路题，掌握技巧即可

代码位置：2\problems\P1644.cpp

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'intdx[]={1,2,1,2};intdy[]={2,1,-2,-1};intb[20][20];// 永远往右走所以不用visintn,m;intdfs(intx,inty){intans=0;if(x==m-1&&y==n-1)return1;_for(i,4){intnx=x+dx[i];intny=y+dy[i];if(nx<0||nx>=m)continue;if(ny<0||ny>=n)continue;ans+=dfs(nx,ny);}returnans;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;n++;m++;// 这道题出的很细，n和m都要+1cout<<dfs(0,0)<<endl;}

2.4.8P1219 八皇后

一道DFS用来搜索的题目，方法就是进阶版的枚举，实际上完全可以通过循环实现（当然会非常繁琐），而使用递归就可以极大地压缩代码，8层循环就改成深度限定为8的递归，然后检查是否满足条件，如果不满足直接终止递归即可。

这里比较麻烦的问题是如何判断是否在同一行、列、对角线上。我使用的方法是使用一个标记数组来记录哪些位置是不能放的，而标记数组的下标就应该是某一个和该行列特定的数字。

对于横排竖列来说是比较简单的，直接用行号和列号即可，而斜着的格子我使用行号列号的和差来标记。代码中rright和lleft数组表示对角线的标记。

至于字典序这个问题就不用考虑了，DFS的特性就决定了得到的答案就是按照字典序排的。

代码位置：2\problems\P1219.cpp

#include<bits/stdc++.h>#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'boolcol[15];introw[15];boolrright[30];// 往左斜boollleft[30];// 往右斜intn;intcnt=0;intdfs(intdepth){intans=0;if(depth==n){if(cnt<3){for(inti=0;i<n;i++){cout<<row[i]+1<<' ';}cout<<endl;cnt++;}return1;}for(inti=0;i<n;i++){if(rright[depth-i+n]||lleft[depth+i]||col[i]){continue;}rright[depth-i+n]=lleft[depth+i]=col[i]=true;row[depth]=i;ans+=dfs(depth+1);rright[depth-i+n]=lleft[depth+i]=col[i]=false;row[depth]=0;}returnans;}intmain(){cin>>n;cout<<dfs(0)<<endl;}