题解 | #迷宫问题#

#include <iostream>
using namespace std;
#include <bits/stdc++.h>
const vector<pair<int,int>>dirs = {{1,0},{0,1},{-1,0},{0,-1}};//顺时针右下左上
pair<int,int> fa[15][15];
void dfs(int x,int y){
    if(x==0&&y==0)return;
    auto t = fa[x][y];
    dfs(t.first,t.second);//深度优先搜索搜索到根节点打印该路径
    printf("(%d,%d)\n",x,y);
}
int main() {
    int m, n;
    cin>>m>>n;
    vector<vector<int>>grip(m,vector<int>(n,0));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin>>grip[i][j];
        }
    }
    //vector<pair<int,int>>track;
    queue<pair<int,int>>q;
    
    q.push({0,0});
    grip[0][0] = 1;
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        
        if(cur.first==m-1 && cur.second==n-1)break;
        for(auto dir : dirs){
            int nextX = cur.first+dir.first;
            int nextY = cur.second+dir.second;
            if(nextX < 0 || nextY<0||nextX>=m||nextY>=n||grip[nextX][nextY]==1)continue;
            fa[nextX][nextY] = cur;//记录下一个节点（nx，ny）的父节点坐标
            q.push({nextX,nextY});
            grip[nextX][nextY] = 1;   
        }
    }
    printf("(%d,%d)\n",0,0);
    dfs(m-1,n-1);
    return 0;
}
// 64 位输出请用 printf("%lld")