题解 | 迷宫问题

#include <iostream>
using namespace std;

#include<queue>
#include<algorithm>
#include<vector>
vector<vector<pair<int,int>>>prevn(101,vector<pair<int,int>>(101));
int g[101][101];
int vit[101][101];
int h,w;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
void bfs(int a,int b){

queue<pair<int,int>>q;
q.push({a,b});
vit[a][b]=1;
while(!q.empty()){
auto it=q.front();
int x=it.first;
int y=it.second;
q.pop();
if(x==h-1&&y==w-1){
    return;
}
for(int i=0;i<4;i++){
int xn=x+dx[i];
int yn=y+dy[i];
if(xn>=0&&xn<h&&yn>=0&&yn<w&&vit[xn][yn]==0&&g[xn][yn]==0){
    q.push({xn,yn});
    vit[xn][yn]=1;
    prevn[xn][yn]={x,y};
}


}



}



}
int main(){
cin>>h>>w;
for(int i=0;i<h;i++){

    for(int j=0;j<w;j++){
        cin>>g[i][j];
    }
}
bfs(0,0);
vector<pair<int,int>>a;
a.push_back({h-1,w-1});
int x=h-1;
int y=w-1;
while(x!=0||y!=0){

    int b=x;
    int c=y;
    x=prevn[b][c].first;
    y=prevn[b][c].second;
    a.push_back({x,y});
}
int n=a.size();
for(int i=n-1;i>=0;i--){
    cout<<'('<<a[i].first<<','<<a[i].second<<')'<<endl;
}

    return 0;
}