题解 | #迷宫问题#

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

void dfs(int x, int y, int M, int N, vector<vector<int> > &Mat, vector<vector<int>  > &Mem, vector<vector<int> > &path, vector<vector<int> > &bestpath){
  
    path.push_back({x,y});
    Mem[x][y]=1;

    // cout<<x<<','<<y<<endl;

    if (x==N-1 && y==M-1){

        bestpath = path;

    }


    vector<int> forward={-1,1};
    for(auto i:forward){
        int x_new = x+i;
        if(x_new<N && x_new>=0 && Mat[x_new][y]==0 && Mem[x_new][y]==0){
            dfs(x_new, y, M, N, Mat, Mem, path, bestpath);
        }
    }

    for(auto j:forward){
        int y_new = y+j;
        if(y_new<M && y_new>=0 && Mat[x][y_new]==0 && Mem[x][y_new]==0){
            dfs(x, y_new, M, N, Mat, Mem, path, bestpath);
        }
    }

    Mem[x][y] = 0;
    path.pop_back();

    // cout<<"back"<<endl;

}

int main() {
    int N, M;
    cin>>N>>M;
    
    vector<vector<int> > Mat(N, vector<int>(M, 0));
    vector<vector<int> > Mem(N, vector<int>(M, 0));
    vector<vector<int> > path;
    vector<vector<int> > bestpath;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>Mat[i][j];
            
        }

    }

    int x=0;
    int y=0;

    dfs(x, y, M, N, Mat, Mem, path, bestpath);

    for(auto it:bestpath){
        cout<<"("<<it[0]<<","<<it[1]<<")"<<endl;
    }


    return 0;

}
// 64 位输出请用 printf("%lld")