题解 | 迷宫问题

#include<vector>
#include <iostream>
#include<queue>
#include<cstring>
using namespace std;
int a[110][110];
queue<pair<int,int>> q;
int n,m;
int dx[]= {0,1,0,-1};
int dy[]={-1,0,1,0};
int st[110][110],dis[110][110];
vector<pair<int,int>> p;
void dfs(int x,int y){
    if(x==n-1&&y==m-1){
        for(auto [xx,yy]:p){
            cout<<"("<<xx<<','<<yy<<")"<<'\n';
        }
    }
    for(int i = 0;i<4;i++){
        int xx = x+dx[i],yy = y+dy[i];
        if(xx<0||xx>=n||yy<0||yy>=m){
            continue ;
        }
        if(a[xx][yy]==0&&st[xx][yy]==0&&dis[xx][yy]>(dis[x][y]+1)){
            st[xx][yy] = 1;

            dis[xx][yy] = dis[x][y]+1;
            p.push_back({xx,yy});
            dfs(xx, yy);
            st[xx][yy] = 0;
            p.pop_back();
        }
    }
}
int main() {
    cin>>n>>m;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin>>a[i][j];
        }
    }
    p.push_back({0,0});
    memset(dis,0x3f,sizeof dis);
    memset(st,0,sizeof st);
    
    st[0][0] = 1;
    dis[0][0] = 0;
    dfs(0,0);


    return 0;
}
// 64 位输出请用 printf("%lld")

采用dfs加回溯的方式，对每个点进行搜索，如果可以到达终点，输出路径即可。

活动地址https://www.nowcoder.com/discuss/726480854079250432