题解 | #迷宫问题#

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

vector<pair<int,int>> path;
vector<pair<int,int>> res;
int x[4] = {1,0,-1,0};
int y[4] = {0,1,0,-1};
void backtrace(vector<vector<int>>& maze,int m,int n,int cur_x,int cur_y){
    // base case
    if( cur_x == m-1 && cur_y == n-1 ){
        res = path;
        return;
    }

    // make choice
    for(int i = 0 ; i < 4; i++){
        int next_x = cur_x + x[i];
        int next_y = cur_y + y[i];
        if( next_x >= 0 && next_x < m &&
            next_y >= 0 && next_y < n && 
            maze[next_x][next_y] == 0 ){

                path.emplace_back(next_x,next_y);
                maze[next_x][next_y] = 1;
                backtrace(maze,m,n, next_x, next_y);
                path.pop_back();
                maze[next_x][next_y] = 0;
        }
    }

}

int main(){
    int m,n;
    cin >> m;
    cin >> n;
    vector<vector<int>> maze(m,vector<int>(n));
    for(int i = 0 ; i< m ; i++){
        for(int j = 0 ; j < n; j++)
            cin >> maze[i][j];
    }
    path.emplace_back(0,0);
    maze[0][0] = 1;
    backtrace(maze,m,n,0,0);


    for(auto x : res)
        cout << '(' << x.first << ',' << x.second << ')' << endl;
}