DFS递归之迷宫问题
DFS递归之迷宫问题:1.能否逃出迷宫;2.逃出迷宫的最短路径;3.缺口迷宫。
DFS之迷宫问题
迷宫问题
本文仅使用 DFS 递归 算法不断回溯来解决迷宫问题,不涉及利用 “栈” 、“队列” 等数据结构来解决问题。
针对于最普通的也是最常见的迷宫问题,总结出相应的模板,不过具体问题还得具体分析,理解之后方才能从容不迫,游刃有余。
一、能否逃出迷宫
最朴素的迷宫问题,通常给定一个
n
×
m
n × m
n×m 的二维字符数组作为迷宫,其中 S
表示起点,#
表示墙,无法通过,.
表示可走的路,T
表示出口,每次只能向上下左右四个方向移动。能逃出迷宫输出 “yes” ,不能则输出 “no”.
逃出这种迷宫,有两个关键点:
一个关键点是:在 DFS 函数中判断能否找到出口,用一个布尔变量记录下来,找到则为真,找不到为假
另一个关键点是:每次递归之后需要回溯,将标记数组重置为0,如果没有重置,那等于说走过一次就不能走了,但实际上后面的搜索中可能还是要走这条路的。
这种题对于已访问的元素,我们不能像 “岛屿问题” 一样简单的把它给 “淹” 了,需要考虑回溯的问题,所以需要使用标记数组 vis[][]
,将已访问标记为
1
1
1 ,递归后再回溯,重置标记数组即可。
下面以计蒜客-T1595为例,判断能否逃出迷宫,完整C++代码如下:
#include <bits/stdc++.h> //万能头文件
using namespace std;
const int N = 110; //定义地图范围,范围开大一点防止数组越界
//#define N 1010 //用define定义的话后面不用加分号
int n, m, ans; //ans用来标记是否找到出口
char mp[N][N]; //迷宫地图数组
int vis[N][N]; //标记数组
void dfs(int x, int y){
if (mp[x][y] == 'T'){
//如果找到了出口,标记为1,再返回
ans = 1;
return;
}
//定义方向数组
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++){
int xx = x + dx[i], yy = y + dy[i];
//如果未越界,可走且未访问
if (xx >= 0 && yy >= 0 && xx < n && yy < m &&
(mp[xx][yy] == '.' || mp[xx][yy] == 'T') && !vis[xx][yy]){
vis[xx][yy] = 1; //标记为已访问
dfs(xx, yy); //递归继续搜索
vis[xx][yy] = 0; //递归搜索完成后回退,将已访问状态重置为未访问
}
}
}
int main(){
//初始化输入数据
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> mp[i][j];
}
}
//标记默认为0
ans = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (mp[i][j] == 'S'){
//找到了起点,开始搜索
dfs(i, j);
}
}
}
//若ans为1,则为真,输出yes;若为0,则为假,输出no
if (ans) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}
二、逃出迷宫的最短路径
与上题一样,唯一不同的是需要计算出每次逃出迷宫的路径,再进行比较得出最短路径。若无法逃出,则输出-1.
以计蒜客-T1596为例,题中 *
为墙,.
为路,完整C++代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int sx, sy; //定义起点坐标
int tx, ty; //定义终点坐标
char mp[N][N]; //迷宫数组
int vis[N][N]; //标记数组
int minx; //记录最短路径
void dfs(int x, int y, int step){
//减枝,用来将之后多余的步数去掉
if (step >= minx)
return;
//找到了终点,比较路径是否最短
if (x == tx && y == ty){
if (step < minx){
minx = step;
}
return;
}
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++){
int xx = x + dx[i], yy = y + dy[i];
//若可走且未访问
if (xx >= 0 && yy >= 0 && xx < n && yy < m &&
(mp[xx][yy] == '.' || mp[xx][yy] == 'T') && vis[xx][yy] == 0){
vis[xx][yy] = 1; //标记为已访问
dfs(xx, yy, step + 1);
vis[xx][yy] = 0; //递归搜索完成后回退,重置为未访问
}
}
}
int main(){
minx = 9999; //保证初始值足够大
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> mp[i][j];
vis[i][j] = 0;
//找到入口
if (mp[i][j] == 'S'){
sx = i;
sy = j;
}
//找到出口
if (mp[i][j] == 'T'){
tx = i;
ty = j;
}
}
}
//标记入口已走过
vis[sx][sy] = 1;
//开始搜索,初始步数为0
dfs(sx, sy, 0);
//输出结果
if (minx == 9999)
cout << "-1" << endl;
else
cout << minx << endl;
return 0;
}
三、缺口迷宫
所谓缺口迷宫,是指迷宫的出口在地图的边界,出口处不一定有像 T
这样的出口符号,而是只有像 .
这样的路。
有些题只需要判断能不能逃出迷宫,有些题则在判断的同时需要计算出最短路径。
这里我们计算下最短路径,与第二种迷宫差不多,只需要将 DFS 函数中迷宫出口的判断条件稍加修改即可。
即将 return 条件由 mp[x][y] == 'T'
改为:mp[x][y] == '.' && (x == 0 || y == 0 || x == n - 1 || y == m - 1)
以计蒜客-T1597为例,题中 @
为起点,#
为墙,.
为路,若无法逃出,则输出
−
1
-1
−1 ,完整的C++代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int sx, sy; //定义起点坐标
int n, m, minx; //定义行、列、最短路径
char mp[N][N]; //迷宫数组
int vis[N][N]; //标记数组
void dfs(int x, int y, int step){
//找到了位于边界上的出口,比较路径是否最短
if (mp[x][y] == '.' && (x == 0 || y == 0 || x == n - 1 || y == m - 1)){
if (step < minx){
minx = step;
}
return;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++){
int xx = x + dx[i], yy = y + dy[i];
//若可走且未访问
if (xx >= 0 && yy >= 0 && xx < n && yy < m && mp[xx][yy] == '.' && vis[xx][yy] == 0){
vis[xx][yy] = 1; //标记为已访问
dfs(xx, yy, step + 1);
vis[xx][yy] = 0; //递归搜索完成后回退,重置为未访问
}
}
}
int main(){
//初始化
minx = 99999999;//保证初始值足够大
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> mp[i][j];
//找到入口
if (mp[i][j] == '@'){
sx = i;
sy = j;
}
}
}
//标记入口已走过
vis[sx][sy] = 1;
//开始搜索,初始步数为0
dfs(sx, sy, 0);
//输出结果
if (minx == 99999999)
cout << "-1" << endl;
else
cout << minx << endl;
return 0;
}
小结
当然,像这种迷宫问题,有很多种解法,这里展示的只是我个人总结下来的一些使用 DFS 递归解题的模板,多多少少也会有点不足。
但也希望能对在看的你有所启发,有所帮助。
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)