题解 | 迷宫问题

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=105;
int mp[N][N];
PII path[N][N];
queue<PII>q;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int h,m;
void bfs(){
    q.push({0,0});
    while(!q.empty()){
        auto pos=q.front();
        if(pos.first==h-1&&pos.second==m-1)return;
        q.pop();
        for(int i=0;i<4;i++){
            int x=dx[i]+pos.first;
            int y=dy[i]+pos.second;
            if(x<0||x>=h||y<0||y>=m)continue;
            if(mp[x][y]==1)continue;
            q.push({x,y});
            mp[x][y]=1;
            path[x][y]=pos;
        }
    }
}

void print(int end_x,int end_y){
    if(end_x==0&&end_y==0)return ;
    int x=path[end_x][end_y].first;
    int y=path[end_x][end_y].second;
    print(x,y);
    cout<<"("<<x<<","<<y<<")"<<endl;
}

int main(){
    cin>>h>>m;
    for(int i=0;i<h;i++){
        for(int j=0;j<m;j++){
            cin>>mp[i][j];
        }
    }
    bfs();
    print(h-1,m-1);
    cout<<"("<<h-1<<","<<m-1<<")"<<endl;
}