目录
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;
}
标签:int,讲解,迷宫,C++,flag,DFS,maze,visited
From: https://www.cnblogs.com/TangYuHeng/p/Cpp_DeepFirstSearch_Preliminary.html