题解 | #迷宫问题#

#include <algorithm>
#include <vector>

using namespace std;

void dfs(vector<vector<int>> &matrix,vector<pair<int,int>> &paths,
         vector<pair<int,int>> &res,int m ,int n ,int i,int j ){
    paths.push_back(make_pair(i, j));
    matrix[i][j]=1;
    if(i==m-1&&j==n-1){
        res=paths;
        return;
    }
    
    
    if((i+1<m)&&matrix[i+1][j]==0){
        dfs(matrix,paths,res,m,n,i+1,j);
    }
    if((i-1>=0)&&(matrix[i-1][j]==0)){
        dfs(matrix,paths,res,m,n,i-1,j);
    }
    if((j+1<n)&&(matrix[i][j+1]==0)){
        dfs(matrix,paths,res,m,n,i,j+1);
    }
    if((j-1>=0)&&(matrix[i][j-1]==0)){
        dfs(matrix,paths,res,m,n,i,j-1);
    }
    matrix[i][j]=0;
    paths.pop_back();
    return ;
}

int main() {
    int m,n;
    while(cin>>m>>n){
        vector<vector<int>> matrix(m,vector<int>(n,0));
        vector<pair<int,int>> paths;
        vector<pair<int,int>> res;
        int temp;
        for(int i =0;i<m;i++){
            for(int j = 0;j<n;j++){
                cin>>temp;
                matrix[i][j]=temp;
            }
        }
        dfs(matrix,paths,res,m,n,0,0);
        for(auto it:res){
            cout<<'('<<it.first<<','<<it.second<<')'<<endl;
        }
    }
}