题解 | #迷宫问题#

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

int main(){
    int N,M;
    cin>>N>>M;
    int rec[N][M];
    int dir[4][2]={-1,0,1,0,0,-1,0,1};
    int cur;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>cur;
            rec[i][j]=cur;
        }
    }
    
    stack<pair<int,int>> stk;
    vector<pair<int,int>> res;
    int cur_i,cur_j;
    int p,q;
    cout<<"(0,0)"<<endl;
    stk.push(make_pair(0,0));
    rec[0][0]=-1;
    int flag=false;
    while(!stk.empty() && !flag){
        cur_i=stk.top().first;
        cur_j=stk.top().second;
        stk.pop();
        for(int i=0;i<4;i++){
            p=cur_i+dir[i][0];
            q=cur_j+dir[i][1];
            if(p>=0 && p<N && q>=0 && q<M && rec[p][q]==0){
                stk.push(make_pair(p,q));
                rec[p][q]=-1;
                res.push_back(make_pair(p,q));
                if(p==N-1 && q==M-1){
                    flag=true;
                    break;
                }
            }
        }
    }
    int k=res.size()-2;
    p=N-1;
    q=M-1;
    while(k>=0){
        cur_i=res[k].first;
        cur_j=res[k].second;
        if(abs(p-cur_i)+abs(q-cur_j)!=1){
            res[k]=make_pair(-1,-1);
        }
        else{
            p=cur_i;
            q=cur_j;
        }
        k--;
    }
    for(int i=0;i<res.size();i++){
        if(res[i].first!=-1){
            cout<<"("<<res[i].first<<","<<res[i].second<<")"<<endl;
        }
    }
}