题解 | #迷宫问题#

• BFS记录路径中当前坐标的上一坐标，fa[i][j]表示坐标(i,j)的路径上的上一坐标
• 遍历fa，输出

#include<bits/stdc++.h>

using namespace std;
int b[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//上下左右四个方向
pair<int,int> fa[15][15];
int BFS(vector<vector<int>> vec,int i,int j,int m,int n);

int main(){
    int n,m;
    while(cin>>n>>m){
        int a;
        vector<vector<int>> vec(n,vector<int> (m,0));
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                cin>>a;
                vec[i][j]=a;
            }
        }
        BFS(vec,0,0,m,n);
        vector<pair<int,int>> res;
        res.push_back(make_pair(n-1, m-1));
        int newn=fa[n-1][m-1].first;
        int newm=fa[n-1][m-1].second;
        res.push_back(make_pair(newn, newm));
        while(newn>=0&&newm>=0){
            if(newn==0&&newm==0)
                break;
            auto tmp=fa[newn][newm];
            res.push_back(tmp);
            newn=tmp.first;newm=tmp.second;
        }
        reverse(res.begin(), res.end());
        for(int i=0;i<res.size();++i)
            cout<<"("<<res[i].first<<","<<res[i].second<<")"<<endl;
        
    }
    return 0;
}

int BFS(vector<vector<int>> vec,int i,int j,int m,int n){
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j)
            fa[i][j]=make_pair(0, 0);
    }
    queue<pair<int, int>> q;
    q.push(make_pair(i, j));
    vector<vector<int>> vis(n,vector<int> (m,0));
    vis[i][j]=1;
    while(!q.empty()){
        pair<int,int> p = q.front();
        q.pop();
        i=p.first;
        j=p.second;
        //找到出口
        if(i==n-1&&j==m-1)
            break;
        //四个方向
        for(int k=0;k<4;++k){
            int newi=i+b[k][0];int newj=j+b[k][1];
            if(newi<0||newi>=n||newj<0||newj>=m)
                continue;
            else{
                if(vis[newi][newj]==0&&vec[newi][newj]==0){
                    q.push(make_pair(newi, newj));
                    vis[newi][newj]=1;
                    fa[newi][newj]=make_pair(i,j);
                }
            }
        }
    }
    return 0;
}