C++ 深度优先搜索(DFS) 讲解
DFS初步概念
DFS是一种深度搜索算法，它的特点是"不撞南墙不回头"，运用递归对不同方向的结果进行搜索。
DFS例题-迷宫游戏
题目描述
这是一个迷宫游戏，有一个n×n的矩阵，矩阵内只能有#或.这两种字符，如果是#则是墙，如果是.则是可以走的路。起点是左上角，终点是右下角，每次只能往上、下、左、右四个方向走。
请你写一个程序，判断这个迷宫是否可以从起点走到终点。
输入输出格式
第1行一个整数n，代表矩阵大小为n×n。
第2~n+1行输入n×n的迷宫矩阵。
输出此迷宫是否能从起点走到终点，可以输出yes，不可以输出no。
输入输出样例
输入#1
5
..##.
#..##
..###
.####
.....
输出#1
yes
输入#2
5
..###
...##
..##.
##...
.##..
输出#2
no
解题思路
用char类型的二维数组maze存储输入的迷宫矩阵，用int类型的二维数组visited存储走过的地方，再用int类型的变量flag记录是否走完迷宫，flag初始值设为0，visited所有元素初始值设为0，maze与visited的下标是对应的，如果maze中的地方是#，则可以将visited相同下标元素的值设为1，再深度搜索可能的情况，若判断成功走到终点，则将flag设为1并结束递归。
代码
#include <bits/stdc++.h>
using namespace std;
char maze[105][105];
int visited[105][105],flag=0,n;
void dfs(int x,int y)//递归搜索函数
{
if(x==n-1&&y==n-1)//走到终点的特判条件
{
flag = 1;
return ;
}
else
{
if(!visited[x-1][y]&&x-1>=0)//上
{
visited[x-1][y] = 1;
dfs(x-1,y);
}
if(!visited[x+1][y]&&x+1<=n-1)//下
{
visited[x+1][y] = 1;
dfs(x+1,y);
}
if(!visited[x][y-1]&&y-1>=0)//左
{
visited[x][y-1] = 1;
dfs(x,y-1);
}
if(!visited[x][y+1]&&y+1<=n-1)//右
{
visited[x][y+1] = 1;
dfs(x,y+1);
}
}
}
int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin >> maze[i][j];
if(maze[i][j]=='#')
{
visited[i][j] = 1;
}
}
}
if(visited[0][0]==1||visited[n-1][n-1]==1)
{
cout << "no" << endl;
return 0;
}
dfs(0,0);
if(flag==1) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}