题解 | #迷宫问题#

回溯法：
要注意的是backTrace的返回值bool，只是为了当出发完成条件后一层一层跳出递归用的
include<bits/stdc++.h>
using namespace std;

bool backTrace(vector<vector<int>>& mat,vector<pair<int,int>>& path,int x,int y){
    vector<int> dir{-1,0,1,0,-1};
    int m = mat.size(),n=mat[0].size();
    if(x == m-1&&y==n-1){
        path.push_back({x,y});
        return true;
    }
    mat[x][y] = 1;
    path.push_back(make_pair(x, y));
    for(int i=0;i<4;++i){
        int r = x +dir[i];
        int c = y +dir[i+1];
        if(r>=0&&r<m&&c>=0&&c<n&&!mat[r][c]){
            if(backTrace(mat,path,r,c)) return true;
        }
    }
    mat[x][y] = 0;
    path.pop_back();
    return false;
}

int main(){
    int m,n;
    cin >> m >> n;
    vector<vector<int>> mat(m,vector<int>(n,0));
    vector<pair<int,int>> path;
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j){
            cin>>mat[i][j];
        }
    
    backTrace(mat,path,0,0);
    for(auto [x,y] : path){
        cout << "("<<x<<","<<y<<")"<<endl;
    }
    
}