深度优先搜索算法（Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索，最糟糕的情况算法时间复杂度为O(!n)，DFS搜索的过程访问可以称之为DFS序。

最近再补搜索，正好遇到这道题，不妨写篇题解加深记忆。

题目

洛谷上似乎没有这道题。大概意思是：

输入正方形迷宫矩阵的边长n，然后换行，输入正方形矩阵（0表示可以通过，1表示墙），再换行，输入s1，s2，e1，e2。分别表示开始点的纵横坐标和结束点的纵横坐标。最后输出YES或NO，判断迷宫是否能走通。

思路

首先这是一道DFS模板题，给定一个起始点，从起始点开始向不同方向枚举（上下左右）判断周围有0的地方，找到后一次深搜下去，直到找到终点，只要没碰到墙就一直往下搜，碰到墙就回溯，一直递归就行了。

代码

定义变量

现在定义一些基本的变量：

#include <bits/stdc++.h>
using namespace std;
//导入头文件
int sx,sy,ex,ey,n,a[110][110],tx,ty;//s，sd表示起始点的xy坐标，ex、ey也是，n代表矩阵的边长，a包含矩阵的信息，tx、ty表示要搜索的方位
int fx[5]={0,1,0,-1,0};
int fy[5]={0,0,1,0,-1};
//fx，fy这两对表示要搜索的方位｛0，0｝是当前的位置，可以忽略，所以从下标1开始，这就是为什么程序中的循环从1开始循环而不是从0开始，之后的｛1，0｝，｛0，1｝……代表方位坐标
bool f = false;//默认没有搜到重点

主函数的编写

是时候编写核心的dfs函数了，如下：

void dfs(int x,int y){//传入点的纵横坐标参数
	cout<<x<<" "<<y<<endl;//做测试用，可不加，输出每一次搜索后的结果
	a[x][y]=1;//标记搜索过的点为1（墙壁），防止死循环
	for(int k=1;k<=4;k++){//枚举点的四个方向
		tx=x+fx[k];
		ty=y+fy[k];
		//上面两行是表示要搜索的点，把x、y坐标给他们，然后加上f~[k]表示坐标值的增减，赋予不同方向点坐标
		if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]==0){//首先判断是否越界（超出矩阵边界），然后确保所处的坐标是没有走过的
			if(tx==ex&&ty==ey) f=true;//判断是否找到终点
			else dfs(tx,ty);//否则，把当前搜到点的坐标拿来再次搜索
		}
	}
}

以上就是dfs函数的编写，为了提高代码运行效率，我们可以在第10行再加上f==false的判断，只要已经找到终点，那么就停止之后没必要的搜索，可以大大节省时间，所以应该是：

if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]==0&&f==false)

main函数的编写

最后编写主函数，如下：

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cin>>a[i][j];	
	}//输入迷宫矩阵
	
	cin>>s>>sd>>e>>ed;//输入出发、结束点
	if(a[sx][sy]==1||a[ex][ey]==1){
		cout<<"NO";
	}//如果起始点或终点有墙那么肯定输出NO
	else{
		dfs(sx,sy);
		if(f==true) cout<<"YES";//如果找到输出YES	
		else cout<<"NO";//否则NO
	}
	return 0;
}

大功告成！

Tips: 注意在输入矩阵时请在0和1之间加上空格，不然会逝的。

完整代码：

#include <bits/stdc++.h>
using namespace std;
//导入头文件
int sx,sy,ex,ey,n,a[110][110],tx,ty;//s，sd表示起始点的xy坐标，ex、ey也是，n代表矩阵的边长，a包含矩阵的信息，tx、ty表示要搜索的方位
int fx[5]={0,1,0,-1,0};
int fy[5]={0,0,1,0,-1};
//fx，fy这两对表示要搜索的方位｛0，0｝是当前的位置，可以忽略，所以从下标1开始，这就是为什么程序中的循环从1开始循环而不是从0开始，之后的｛1，0｝，｛0，1｝……代表方位坐标
bool f = false;//默认没有搜到重点

void dfs(int x,int y){//传入点的纵横坐标参数
	cout<<x<<" "<<y<<endl;//做测试用，可不加，输出每一次搜索后的结果
	a[x][y]=1;//标记搜索过的点为1（墙壁），防止死循环
	for(int k=1;k<=4;k++){//枚举点的四个方向
		tx=x+fx[k];
		ty=y+fy[k];
		//上面两行是表示要搜索的点，把x、y坐标给他们，然后加上f~[k]表示坐标值的增减，赋予不同方向点坐标
		if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]==0&&f==false){//首先判断是否越界（超出矩阵边界），然后确保所处的坐标是没有走过的
			if(tx==ex&&ty==ey) f=true;//判断是否找到终点
			else dfs(tx,ty);//否则，把当前搜到点的坐标拿来再次搜索
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cin>>a[i][j];	
	}//输入迷宫矩阵
	
	cin>>sx>>sy>>ex>>ey;//输入出发、结束点
	if(a[sx][sy]==1||a[ex][ey]==1){
		cout<<"NO";
	}//如果起始点或终点有墙那么肯定输出NO
	else{
		dfs(sx,sy);
		if(f==true) cout<<"YES";//如果找到输出YES	
		else cout<<"NO";//否则NO
	}
	return 0;
}

Coding愉快！