前言

最近本人在做 WolvCTF 的时候遇到了一个特别有意思的迷宫题，在写dfs的时候遇到了一些问题（www，本人高中还是信竞生，连个dfs都写不出来，这是太没用了……）最后由本人在之前写过的一道简单的迷宫题题解中得到了启发，在此阐释一下我对迷宫中dfs的模板理解。

当然，本人的理解基于自己在高中时学过的知识，可能带有个人风格，读者可以按照自己的习惯来

一道简单的迷宫题，但已经基本有了迷宫题的dfs所具有的特征

我们先看那一道比较简单的dfs是如何写的

题目是NSSCTF平台上的sadmaze题目，在本人的个人做题记录中有

这个迷宫的地图是这样的：

1111111111111111111111111111111
1S00100010000010000000000000001
1110111010101111101111101111101
1010001000100000100000100000101
1011101011101110111110111011111
1000101000101010000010101000001
1011101110111011101110101110101
1000000010001010001000001010101
1011111111101011101111101011101
1000100000000010100000101010001
1110111011101010111110101011101
1000001000101000000010000000101
1111101111111111111011111111101
1010000000000010101010000000001
1011111111101010101011101111111
1010001000101010001000100000001
1011101110111010111011111111101
10100010000010101000001T1000001
1010101010111010101111101110101
1000100010001010000010000010101
1011111110101011111010111110101
1010001010101000101000100000101
1010111011101011101110101111101
1000100000001010000010100010101
1110101111101011101011101110101
1010100000101000001000001010001
1010111110111111111111111010101
1000000010000010000000001000101
1111101110101110111110101011111
1000001000100000001000100000001
1111111111111111111111111111111

走迷宫的规则是这样的，S是起点，T是终点，1不能碰，0可以碰

先贴上本人的dfs代码（当时这份代码本人一次就写对了，呜呜呜）

代码语言C++

#include<bits/stdc++.h>
using namespace std;
char Map[81889]={
	0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 
  0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31,
  ****** 
}
char map[31][31];//用于记录地图，同时也用来标记是否已经走过这个位置
char t[1000];//记录这条路径从起点到当前位置的操作
int r=0;//记录当前路径从起点到当前位置的步数
int dx[4]={-1,0,1,0};//x方向的移动
int dy[4]={0,1,0,-1};//y方向的移动
char op[4]={'w','d','s','a'};//操作 w是上 d是右 s是下 a是左 与dx[]和dy[]是对应的
bool check(int qx,int qy){//检查这个点是否合法 
	if(qx>=0&&qx<31&&qy>=0&&qy<31){
		if(map[qx][qy]=='0'||map[qx][qy]=='T')return 1;
	}
	return 0;
} 
void dfs(int x,int y){//深搜基本功 
	if(map[x][y]=='T'){//找到终点了！
		for(int i=0;i<r;i++)cout<<t[i];
		cout<<endl;
		cout<<r;
		cout<<endl;
		return;
	}
	for(int i=0;i<4;i++){//向四个方向前进
		int qx=dx[i]+x;//对x进行移动
		int qy=dy[i]+y;//对y进行移动
		if(check(qx,qy)){//检查移动之后的点是否合法（在进入移动后的点的dfs之前检查）
            			//其实这里还有一种方法就是不在这里检查，
            			//而是在进入当前点的dfs函数之后检查
            			//但是这一种方法笔者经常容易和这个代码的方法混用
            			//因此笔者决定以后都用这个方法
			t[r]=op[i];//记录操作
			r++; 		//路径长度增加
			map[x][y]='1';//这是重点！！！
            				//标记当前位置已经走过
			dfs(qx,qy); 	//进入这个移动之后的点的dfs函数
			map[x][y]='0'; //回溯，从这里往后的代码要和前面的代码一一对应,
            				//顺序相反，反向操作
            				//因为dfs(qx,qy)函数出来之后
            				//从(x,y)向(qx,qy)的之后的所有路径已经全部被执行完了
            				//因此要将所有的东西全部修复为从(x,y)移动之前的状态
			r--;			
			t[r]=0;
		}
	}
}
int main(){
	for(int i=0;i<31;i++){
		for(int j=0;j<31;j++){
			//cout<<Map[1100*i+j];
			map[i][j]=Map[1100*i+j];
		}
		//cout<<endl;
	}
	for(int i=0;i<31;i++){//输出迷宫图案 
		for(int j=0;j<31;j++){
			 cout<<map[i][j]<<"  ";
		}
		cout<<endl;
		cout<<endl;
	}
	dfs(1,1);//调用深搜函数 
	/*int sx=1,sy=1;//这里是手动检验 
	while(1){
		char a;
		cin>>a;
		if(a=='a'){
			sy--;
		}
		if(a=='w'){
			sx--;
		}
		if(a=='s'){
			sx++;
		}
		if(a=='d'){
			sy++;
		}
		if(check(sx,sy)){
			cout<<"yes"<<" "<<sx<<" "<<sy<<endl;
		}
		else cout<<"no"<<" "<<sx<<" "<<sy<<endl;
	}*/
	return 0;
}

dfs处的代码我已经全部给写了注释

在此总结一下走迷宫用的dfs函数的模板

dfs函数前的处理

要定义几个数组，用来表示向不同方向移动时x和y的变化量，这里就是dx[4]和dy[4]
定义一个长度会随着dfs函数深入而边长的数组，用来记录移动操作所要输入的字符，可以用vector，也可以像我一样定义一个长度和一个足够长的数组，这里就是r和t[1000]
和上一点相对应的，也要有一个表示向不同方向移动时所要输入的字符数组，必须要和dx和dy数组所表示的方向一致
定义一个二维数组，用来记录是否已经走过。这个数组可以和原来的地图数组相重合，具体看情况，这里就是map[31][31]。这个数组非常重要，如果没有这个数组，你dfs就会往回走！
定义一个check(int x,int y)的函数，用来检验这个移动之后的点是否合法

dfs内部实现

终点处理

首先要进行是否是终点的判断，如果是终点，就要输出之前所记录的全部路径

if(map[x][y]=='T'){//找到终点了！
		for(int i=0;i<r;i++)cout<<t[i];
		cout<<endl;
		cout<<r;
		cout<<endl;
		return;
	}

向不同方向延伸的循环

在这个循环中，要先进行x和y的变化，再检查移动之后的坐标是否合法

int qx=dx[i]+x;//对x进行移动
int qy=dy[i]+y;//对y进行移动
if(check(qx,qy)){

如果移动之后的点合法，那我们就要正式的移动了，移动前，我们要先将路径数组给记录上

t[r]=op[i];//记录操作
r++; 		//路径长度增加

然后再记录这个点被我们走过了

map[x][y]='1';//这是重点！！！
            //标记当前位置已经走过

当然以上两个操作可以颠倒，但是第一个操作（记录路径）的顺序不能颠倒，读者可以考虑一下为什么

之后就正式的走这个点了

dfs(qx,qy)

在这里不对递归的实现进行讲解，读者请自行了解（其实就是在函数里又调用了一个函数，只不过恰巧是当前这个函数而已）

所要注意的是，dfs(qx,qy) 函数调用完成后，就表明从(x,y)到（qx,qy）以及之后的路径已经全部执行完了

因此之后就要回溯，将我们之前的操作都还原

map[x][y]='0'; //回溯，从这里往后的代码要和前面的代码一一对应,
            				//顺序相反，反向操作
            				//因为dfs(qx,qy)函数出来之后
            				//从(x,y)向(qx,qy)的之后的所有路径已经全部被执行完了
            				//因此要将所有的东西全部修复为从(x,y)移动之前的状态
			r--;			
			t[r]=0;

dfs调用

我们这个dfs调用只需要从起点开始执行即可。

dfs(1,1);//调用深搜函数

以上就是一个走迷宫所要使用的dfs函数模板了，我们之后再依照WolvCTF中的ej题目进行讲解