迷宫游戏(c++)

我们来玩一个迷宫游戏，尝试走一下面的迷宫。

迷宫游戏
我们用一个二维的字符数组来表示前面画出的迷宫：

S**.
....
***T

其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。你需要从S出发走到T，每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一次。你需要编程来求解出一种从起点到终点的走法。

很明显，当我们从任意格子出发，都有可能往四个方向走：上，下，左，右。而初始的时候，我们是在起点S处，之后开始进行我们的搜索过程，也就是我们要讲的 DFS 算法。

那么当我们搜索到了某一个格子（也就是我们下一步会从该格子出发的时候）：

1.首先要判断一下当前格子是否就是终点，如果是，那么就表示我们已经成功的从起点S移动了若干步之后到达了终点T，便成功地完成了这个问题。

2.否则我们就需要从该格子出发，可以分别枚举向左、向下、向右、向上四个方向，依次去判断它旁边的四个点是否可以作为下一步合法的目标点，如果可以，那么我们就进行这一步，走到目标点，然后继续进行操作。

3.当然有可能左、下、右、上四个点都无法再成为合法的目标点了，那么我们就回退一步，然后从上一步所在的那个格子向其他 未尝试的方向 继续枚举。

关于合法的定义如下：

必须在所给定的迷宫范围内。 如样例中是一个 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;
}