题解 | #迷宫问题#

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

int m, n;
vector<vector<int>> maze;
vector<pair<int, int>> route;
vector<pair<int, int>> bestRoute;
void backTrack(int i, int j, vector<pair<int, int>>& route){
    if(i < 0 || j < 0 || i >= m || j >= n || maze[i][j] == 1) return;
    maze[i][j] = 1;
    route.push_back({i, j});
    if(i == m-1 && j == n-1){
        bestRoute = route;
        return;
    }
    backTrack(i-1, j, route);
    backTrack(i+1, j, route);
    backTrack(i, j-1, route);
    backTrack(i, j+1, route);
    maze[i][j] = 0;
    route.pop_back();
}

int main(){
    cin >> m >> n;
    maze = vector<vector<int>>(m, vector<int>(n, 0));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> maze[i][j];
        }
    }
    backTrack(0, 0, route);
    for(auto it : bestRoute){
        cout << "(" << it.first << "," << it.second << ")" << endl;
    }
    return 0;
}