迷宫游戏的DFS算法解析与C++实现
迷宫游戏的DFS算法解析与C++实现
我们来玩一个迷宫游戏，尝试走一下面的迷宫。
迷宫游戏
我们用一个二维的字符数组来表示前面画出的迷宫：
S**.
....
***T
其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。你需要从S出发走到T，每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一次。你需要编程来求解出一种从起点到终点的走法。
很明显，当我们从任意格子出发，都有可能往四个方向走：上，下，左，右。而初始的时候，我们是在起点S处，之后开始进行我们的搜索过程，也就是我们要讲的 DFS 算法。
那么当我们搜索到了某一个格子（也就是我们下一步会从该格子出发的时候）：
首先要判断一下当前格子是否就是终点，如果是，那么就表示我们已经成功的从起点S移动了若干步之后到达了终点T，便成功地完成了这个问题。
否则我们就需要从该格子出发，可以分别枚举向左、向下、向右、向上四个方向，依次去判断它旁边的四个点是否可以作为下一步合法的目标点，如果可以，那么我们就进行这一步，走到目标点，然后继续进行操作。
当然有可能左、下、右、上四个点都无法再成为合法的目标点了，那么我们就回退一步，然后从上一步所在的那个格子向其他 未尝试的方向 继续枚举。
关于合法的定义如下：
必须在所给定的迷宫范围内。 如样例中是一个 4 行 3 列的迷宫，那么这个点必须在 (0,0)−(3,2) 的范围中才能称为合法，否则即为不合法。
这个点在搜索过程中必须没有被访问过。 也就是说，一个点在 DFS 的过程中只能被访问一次，不能重复访问。这样做是因为，如果一个点允许多次访问，那么肯定会出现死循环的情况——在两个点中间来回走。不过，根据题意，在某些情况下，你回溯了之后可以视回溯前的点为没有访问过。
这个点必须不是墙壁。这个显然很好理解，我们只能走在平地上，不能走在墙壁上也不能穿过墙壁。
DFS 走迷宫对应的伪代码框架如下：
// 对坐标为 (x, y) 的点进行搜索
bool dfs(int x, int y) {
if (x, y) 是终点 {
// 找到了路径
return true;
}
// 标记 (x, y) 已经访问
// 向上走到位置 (tx, ty)
if (tx, ty) 合法 {
if (dfs(tx, ty) == true) {
// 递归调用 DFS 函数，将(tx, ty)作为当前状态进行搜索，下同。
return true;
}
}
// 向左走到位置 (tx, ty)
if (tx, ty) /* 合法 */ {
if (dfs(tx, ty) == true) {
return true;
}
}
// 向下走到位置 (tx, ty)
if (tx, ty) /* 合法 */ {
if (dfs(tx, ty) == true) {
return true;
}
}
// 向右走到位置 (tx, ty)
if (tx, ty) /* 合法 */ {
if (dfs(tx, ty) == true) {
return true;
}
}
return false;
}
迷宫搜索2(输出路径）：
#include <iostream>
#include <string>
using namespace std;
int n, m;
string maze[110];
int sx, sy;
bool vis[110][110];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
bool dfs(int x, int y) {
vis[x][y] = true;
if (maze[x][y] == 'T') {
return true;
}
maze[x][y] = 'm';
for (int i = 0; i < 4; i++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
if (dfs(tx, ty)) {
return true;
}
}
}
maze[x][y] = '.';
return false;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> maze[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'S') {
sx = i;
sy = j;
}
}
}
if (dfs(sx, sy)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
for(int i = 0; i < n; i++){
cout << maze[i] << endl;
}
return 0;
}