简单DFS手把手教程以及适应性修改
对于比赛而言，DFS(深度优先搜索)是个十分常见的考点，然而DFS对许多新手的编写不是很友好，比如其“较难理解和容易混淆的代码”，或者“看到题目知道考点是DFS却无从下手”这些我也常犯的错误，因此，本菜鸡便写了以下的思维帮助萌新对DFS更容易上手（1，讲述基本DFS代码的实现；2，变形DFS题目的思维和修改操作；3，为简化知识点，本篇不采用STL方法，仅以递归实现）。
参考题目来源：
1.(基本DFS)走迷宫
2.(最短路DFS)贪吃蛇
3.(多终点最短路DFS)迷宫
4.(多起终点计步DFS)迷宫搜索plus
一 · 基本DFS代码的实现
案例：(基本DFS)走迷宫
问题与描述：
给一张个迷宫，问能否从起点走到终点，只能往上下左右走，不能斜着走
多组测试数据，每组第一行两个正整数，分别为n和m，表示n这个迷宫有n行m列(0<n,m<10)；
接着是n行m列，’#'表示路，‘*’表示墙，‘S’表示起点，‘T’表示终点。
每组测试数据输出一个结果，如果能从S走到T，输出“YES”,否则输出“NO”
1.基本设置
(尽量要设置为全局变量，毕竟很多要被自定义函数引用)
首先，是main函数的准备和变量名的定义:
①迷宫 n*m 的读入
②起点 S 读入
③注意每一读入一行要用 scanf(" ") 吸收空格
*本菜鸟发现在部分OJ上用 getchar() 吸收似乎会出问题
④考虑到后面递归时需要地图标记来判断是否走过，则加个数组vis
⑤加一个 flag 来标记是否能走到终点
#include<bits/stdc++.h>
using namespace std;
int n,m;//地图大小
char the_map[100][100];//地图
int vis[100][100];//地图标记
int flag=0;
int main(){
int stx,sty;//起点坐标
while(~scanf("%d %d",&n,&m)){
for(int i=1;i<=n;i++){
scanf(" ");
for(int j=1;j<=m;j++){
scanf("%c",&the_map[i][j]);//读入地图
if(the_map[i][j]=='S'){
stx=i;sty=j;
}//存入起点
}
}
memset(vis,0,sizeof(vis));//清零
flag=0;//判断重置
if(flag==1){//是否可以走到终点
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
这样，剩下的任务就是写核心递归了。
2.递归编写
现在，我们整理一下要面对的问题和解决代码：
①自定义函数需要放在主函数的哪里？
：考虑到有多次读入，那就要放在清零后
②自定义函数里四个方位怎么判断？
：我们在全局里设置这两个方向数组来操控行走的方向
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
：在递归中，我们要自行设置行走规律，就是一个跑4次的for循环来代表四个方向
for(int c=0;c<4;c++){
x=x+dx[c];//x,y代表当时的位置,这样利用dx,dy数组给x,y重新赋值
y=y+dy[c];//相当于x和y的加加减减，即上下左右的移动
}
③如果遇到了终点，该怎么办？
：那很好办，来个if，标记已走到终点，可以返回
if(the_map[x][y]=='T'){
flag=1;return;
}
④避免走重复的路怎么解决？
：利用上述的地图标记来解决
if(vis[x][y]==1) return;//返回
else vis[x][y]=1;//到此一游
⑤如果碰到了墙该怎么办？
：有两种墙，一种是类似于游戏中的空气墙(地图边界)，DFS的硬性要求是不准超出空气墙，另一种是迷宫里的自己设定的墙
if(x>=1&&x<=n&&y>=1&&y<=m){//游戏里的空气墙，即地图边界
if(the_map[x][y]!='*'){//撞墙
？？？
}
}
：上面代码？？？是要考虑到底是 return 好还是 重新择路 好，由于当前状况无法分析出原因，暂且保留。
3.递归的拼装
我们要将上面几个代码在自定义函数里排好顺序，才能使DFS正常工作。
现在根据正常思路，从起点开始，一旦进入了自定义函数里，那么必须标记一下到此一游(④)，紧接着，为了防止在不知道它是不是终点的情况下就直接进入了走方向的环节，我们必须先判断终点(③)，然后便是方向判断和碰到墙的选择，我们发现：由于地图标记的存在，必须预知下个方向是否撞墙或发生其他事情，才能避免地图标记卡死，否则会让转弯就可以走的路硬生生的走不通，因此，？？？处只能是填 重新择路 ，并且，还要将撞墙嵌入方向判断，从而使每个方向都能进行预知和改变(②包⑤)。不过，在拼装的最后一步时，由于存在某些方向会撞墙的情况，若仅用一种变量去重新赋值，那么会出现return后此变量值已被覆盖的情况，也将使某些可走的道路走不通，所以要对四个方向里的坐标进行新的变量定义，以此来使递归能用两类变量交替运行。
因此，我们能整理出以下的代码：
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void mp(int x,int y){//没有输出，全靠flag,用void,读入两个坐标
if(vis[x][y]==1) return;//返回
else vis[x][y]=1;//到此一游
if(the_map[x][y]=='T'){
flag=1;return;
}
int xx,yy;//xx,yy和x,y交替的变量
for(int c=0;c<4;c++){
xx=x+dx[c];//x,y代表当时的位置,这样利用dx,dy数组给x,y重新赋值
yy=y+dy[c];//相当于x和y的加加减减，即上下左右的移动
if(xx>=1&&xx<=n&&yy>=1&&yy<=m){//游戏里的空气墙，即地图边界
if(the_map[xx][yy]!='*'){//撞墙
mp(xx,yy);
}
}
}
}
4.完整代码
这样就整理出了一个最基础的DFS
#include<bits/stdc++.h>
using namespace std;
int n,m;
char the_map[100][100];
int vis[100][100];
int flag=0;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void mp(int x,int y){
if(vis[x][y]!=0){
return;
}else{
vis[x][y]=1;
}
if(the_map[x][y]=='T'){
flag=1;
return;
}
int xx,yy;
for(int c=0;c<4;c++){
xx=x+dx[c];
yy=y+dy[c];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
if(the_map[xx][yy]!='*'){
mp(xy,yy);
}
}
}
}
int main(){
int stx,sty;
while(~scanf("%d %d",&n,&m)){
for(int i=1;i<=n;i++){
scanf(" ");
for(int j=1;j<=m;j++){
scanf("%c",&the_map[i][j]);
if(the_map[i][j]=='S'){
stx=i;sty=j;
}
}
}
memset(vis,0,sizeof(vis));
flag=0;
mp(stx,sty);
if(flag==1){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
二 · 不同DFS题目的适应性修改(1)
案例：(最短路DFS)贪吃蛇
问题与描述：
在一个n*m的迷宫中，有一条小蛇，地图中有很多围墙，猥琐的出题者用“#”表示，而可以走的路用“.”表示，小蛇他随机出生在一个点上，出生点表示为“S”，他想抵达的终点表示为“E”，小蛇有一个奇怪的能力，他每走一格便会增长一格，即他走了一格后，他的尾巴不会缩回。小蛇想知道他怎么到达他想去的地方，请你帮助他。PS：每格长1米，贪吃蛇规定不能撞墙，不能咬自己的身体。
第一行：输入N,M；
第二行：输入S的坐标Xs，Ys，E的坐标Xe，Ye;
后面的N行：每行输入M个数，描述每一行的情况。
输出一个数，小蛇到达终点的最短距离（单位：cm），若无法达到，输出-1。
1.思考变化
和基础的DFS相比，这题多了一个最短距离，那么，我们便要考虑加一个变量来储存总最短路径以及一个变量来存储每次走的步数。当然，在初始时，总最短路径应该取超级大，好让计步比较赋值
int minn,cnt;//总最短路径和计步
minn=10000000;//需要放在main函数里作初始化最大
但是还有个难题，由于地图标记非1即0，也许return时会产生重叠，从而影响了我们计步，所以为解决多条路径计步的麻烦，我们可以假设走过的路都用墙堵上（同样，这个放墙只能提前判断，因此必须放在方向里面）然后，在没有碰到墙的情况下进入下一个节点(同时计步加一)，并且假设当这个节点内的路都走完退出后，再把墙推倒，这样就能防止计步的重复或缺失。
the_map[xx][yy]='#';
mp(xx,yy,cnt+1);
the_map[xx][yy]='.';
对于计步和总最短路径的比较，需要知道一个原则，那就是DFS会将所有的走法都跑一遍，也就是说，我们可以在找到了终点(这只是其中一条路)的时候和总最短路径比较和取舍。
if(xx==ex&&yy==ey){//找到终点了
if(cnt<minn) minn=cnt; //比较和赋值
ok=1;
}
由于需要计步，那么我们需要在自定义函数里加一个计步变量，表示从0开始。
fk(sx,sy,0);
2.代码实现
最后，再把起点终点的查找方式和输出的内容修改一下便完成了：
#include<bits/stdc++.h>
using namespace std;
char mp[100][100];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ok=0;
int n,m,minn,cnt;
int sx,sy,ex,ey;
void fk(int x,int y,int cnt){
int xx,yy;
for(int i=0;i<=3;i++){
xx=x+dx[i];
yy=y+dy[i];
if(xx<n&&yy<m&&xx>=0&&yy>=0){
if(mp[xx][yy]!='#'){
if(xx==ex&&yy==ey){
if(cnt<minn) minn=cnt;
ok=1;
}else{
mp[xx][yy]='#';
fk(xx,yy,cnt+1);
mp[xx][yy]='.';
}
}
}
}
}
int main(){
while(~(scanf("%d%d",&n,&m))){
memset(mp,0,sizeof(mp));
cin>>sx>>sy>>ex>>ey;
sx--;sy--;
ex--;ey--;//由于我是从0到n-1读入，因此都要减一
for(int i=0;i<n;i++){
scanf(" ");
for(int j=0;j<m;j++){
scanf("%c",&mp[i][j]);
}
}
ok=0;
minn=100000;
fk(sx,sy,0);
if(ok==1){
cout<<(minn+1)*100<<endl;
}else{
printf("-1\n");;
}
}
return 0;
}
二 · 不同DFS题目的适应性修改(2)
案例：(多终点最短路DFS)迷宫
问题与描述：第一行输入两个整数n和m，表示这是一个n*m的迷宫。
接下来的输入一个n行m列的迷宫。其中’@‘表示你的位置，’#‘表示墙，你无法通过，’.‘表示路，你可以通过’.‘移动，所有在迷宫最外围的’.'都表示迷宫的出口（你每次只能移动到四个与他相邻的位置——上，下，左，右）。
输出整数，表示你逃出迷宫的最少步数，如果你无法逃出迷宫输出-1(1<=n,m<=10)
1.思考变化
迷宫的边缘一圈是有好多出口的，那么我们只要判断如果最外围一圈是‘.’那就能走出迷宫和比较最短路，而多条路径比较导致上述的“堵墙，拆墙法”不变。
if(xx==1||yy==1||xx==n||yy==m){//边缘
if(cnt<minn)minn=cnt;
ok=1;
}
2.代码实现
所以，整体代码便很相似：
#include<bits/stdc++.h>
using namespace std;
char mp[100][100];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ok=0;
int n,m,minn,cnt;
int sx,sy;
void fk(int x,int y,int cnt){
int xx,yy;
for(int i=0;i<=3;i++){
xx=x+dx[i];
yy=y+dy[i];
if(xx<=n&&yy<=m&&xx>=1&&yy>=1){
if(mp[xx][yy]=='.'){
if(xx==1||yy==1||xx==n||yy==m){
if(cnt<minn)minn=cnt;
ok=1;
}
mp[xx][yy]='#';
fk(xx,yy,cnt+1);
mp[xx][yy]='.';
}
}
}
}
int main(){
while(~(scanf("%d%d",&n,&m))){
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++){
scanf(" ");
for(int j=1;j<=m;j++){
scanf("%c",&mp[i][j]);
if(mp[i][j]=='@'){
sx=i;sy=j;
}
}
}
ok=0;
minn=100000;
fk(sx,sy,1);
if(ok==1){
cout<<minn<<endl;
}else{
printf("-1\n");
}
}
return 0;
}
二 · 不同DFS题目的适应性修改(3)
1.思考变化
案例：(多起终点计步DFS)迷宫搜索plus
问题与描述：
迷宫的游戏，相信大家都听过，现在我们用一个nm的矩阵表示一个迷宫，其中‘S’表示起点，‘D’表示终点，‘X’表示该位置为墙，不可以走，‘.’表示可以通行。每次只能向“上下左右”四个方向移动一步。
你的任务是判断在x步内（小于等于x），能否从起点走到终点。
本题可能存在多个起点和多个终点，只要有一个满足条件即可。
第一行输入三个数n m x，分别表示迷宫的尺寸和步数。（1 < n，m < 7； 0 < x < 50）接下来输入一个nm的矩阵，描述迷宫的状态。判断是否能在x步内从起点走到终点，如果可以，输出“YES”，否则输出“NO”。
1.思考变化
迷宫有好多起点和终点，对于正常思路而言是加一个数组去记录这样的起点和终点是否走过，而本菜鸡考虑到可以在main函数里再遍历一遍地图，一旦找到一个起点，那就进入DFS，这样也可以把所有的起点都遍历一遍。而对于终点而言，就是上述的多终点样例了(由于这题不需要计步，那就把计步的内容删去/其实保留也没影响)。
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='S'&&start[i][j]==0){
start[i][j]=1;//遍历地图来一一找到起点
fk(i,j,1);
}
}
}
2.代码实现
#include<bits/stdc++.h>
using namespace std;
char mp[100][100];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ok=0;
int start[100][100]={0};
int n,m,minn,cnt;
int sx,sy,x;
void fk(int x,int y,int cnt){
int xx,yy;
for(int i=0;i<=3;i++){
xx=x+dx[i];
yy=y+dy[i];
if(xx<=n&&yy<=m&&xx>=1&&yy>=1){
if(mp[xx][yy]!='X'&&mp[xx][yy]!='S'){
if(mp[xx][yy]=='D'){
if(cnt<minn)minn=cnt;
ok=1;
return;
}
mp[xx][yy]='X';
fk(xx,yy,cnt+1);
mp[xx][yy]='.';
}
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&x);
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++){
scanf(" ");
for(int j=1;j<=m;j++){
scanf("%c",&mp[i][j]);
}
}
ok=0;
minn=100000;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='S'&&start[i][j]==0){
start[i][j]=1;
fk(i,j,1);
}
}
}
if(ok==1&&minn<=x){
cout<<"YES"<<endl;
//cout<<minn<<endl;
}else{
cout<<"NO"<<endl;
}
return 0;
}
总结
其实我们不难发现，只要学会了最基础的DFS，那么对于题目的变形也就可以以不变应万变。