这个走迷宫代码是怎么实现回溯的(关键词-#include)

Question

这个走迷宫代码是怎么实现回溯的？

#include<bits/stdc++.h>
using namespace std;
int n,m;
string maze[110];//字符串数组当二维数组使用 
bool vis[110][110];//把走过的路标记 
bool in(int x,int y){//保证不超出地图 
    return 0<=x&&x<n&&0<=y&&y<m;
}
bool dfs(int x,int y){//开头判断是否到 
    if(maze[x][y] == 'T'){
        return true;
    }
    vis[x][y]=1; 
    maze[x][y]='m';
    int tx=x-1,ty=y;//上左下右逆时针搜索 
    if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){
        if(dfs(tx,ty)){//搜前判断前面是不是墙或空有没有走过 
            return true;
        }
    }
    tx=x,ty=y-1;
    if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){
        if(dfs(tx,ty)){
            return true;
        }
    }
    tx=x+1,ty=y;
    if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){
        if(dfs(tx,ty)){
            return true;
        }
    }
    tx=x,ty=y+1;
    if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){
        if(dfs(tx,ty)){
            return true;
        }
    }//上下左右都不能走，取消标记回退 
    vis[x][y]=0;
    maze[x][y]='.';
    return false;//返回上一层递归 
} 
int main(){
    cin>>n>>m;//输入地图 
    for(int i=0;i<n;i++){
        cin>>maze[i];
    }
    int x,y;//先找起点 
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maze[i][j]=='S'){
                x=i;y=j;
            }
        }
    }
    if(dfs(x,y)){//开始搜索 
        for(int i=0;i<n;i++){
            cout<<maze[i]<<endl;
        }
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

Answer 1

下午好🌅🌅🌅
本答案参考通义千问

在这个走迷宫的代码中，回溯是通过深度优先搜索（DFS）实现的。当算法到达一个死胡同时（即当前节点没有未访问的邻居），它会取消当前节点的访问标记，并将当前位置恢复为初始状态（通常是空格'.'）。这样，算法就能回溯到上一步继续尝试其他路径。

以下是代码中的关键部分和对应的注释，展示了如何实现回溯：

if(dfs(tx,ty)){//搜前判断前面是不是墙或空有没有走过 
    return true;
}

这段代码表示如果下一步的搜索成功（即找到终点'T'），则返回true。如果失败，则继续回溯。

vis[x][y]=0;
maze[x][y]='.';
return false;//返回上一层递归 

这段代码表示如果所有方向都无法继续前进（即当前节点的所有邻居都被访问过或者不可通行），则取消当前节点的访问标记，并将其恢复为空格'.'。然后返回false，表示需要回溯到上一步。

下面是有序列表形式的解决方案步骤：

1. 定义迷宫：使用字符串数组maze[110]来存储迷宫布局。
2. 定义访问标记：使用二维布尔数组vis[110][110]来记录已经访问过的路径。
3. 检查边界条件：函数in(int x, int y)确保坐标在迷宫范围内。
4. 定义DFS函数：bool dfs(int x, int y)用于执行深度优先搜索。
5. 标记当前节点：在进入新节点之前，将当前节点标记为已访问，并设置为迷宫中的特殊字符（如'm'）。
6. 尝试四个方向：依次尝试向上下左右四个方向移动。
7. 回溯处理：如果所有方向都无法继续前进，则取消当前节点的访问标记，并将其恢复为空格'.'，然后返回false以触发回溯。

以下是修改后的代码，强调了回溯部分：

#include<bits/stdc++.h>
using namespace std;

int n, m;
string maze[110]; // 字符串数组当二维数组使用
bool vis[110][110]; // 把走过的路标记

bool in(int x, int y) { // 保证不超出地图
    return 0 <= x && x < n && 0 <= y && y < m;
}

bool dfs(int x, int y) { // 开头判断是否到终点
    if (maze[x][y] == 'T') {
        return true;
    }
    vis[x][y] = 1;
    maze[x][y] = 'm';

    // 上左下右逆时针搜索
    int tx = x - 1, ty = y;
    if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
        if (dfs(tx, ty)) { // 搜前判断前面是不是墙或空有没有走过
            return true;
        }
    }

    tx = x, ty = y - 1;
    if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
        if (dfs(tx, ty)) {
            return true;
        }
    }

    tx = x + 1, ty = y;
    if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
        if (dfs(tx, ty)) {
            return true;
        }
    }

    tx = x, ty = y + 1;
    if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
        if (dfs(tx, ty)) {
            return true;
        }
    }

    // 上下左右都不能走，取消标记回退
    vis[x][y] = 0;
    maze[x][y] = '.';
    return false; // 返回上一层递归
}

int main() {
    cin >> n >> m; // 输入地图
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }

    int x, y; // 先找起点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == 'S') {
                x = i;
                y = j;
            }
        }
    }

    if (dfs(x, y)) { // 开始搜索
        for (int i = 0; i < n; i++) {
            cout << maze[i] << endl;
        }
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

以上代码展示了如何在迷宫问题中实现回溯，通过DFS遍历迷宫，并在无法继续前进时取消当前节点的访问标记，从而实现回溯。