题解 | #迷宫问题#

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


vector<pair<int, int> > res;
void dfs(vector<vector<int>>& matrix, int n, int m, int i, int j, vector<pair<int, int>>& paths){
    //记录 与 回溯的过程。

    // 进入该路径，标记为一，下次不再走这条路径
    paths.push_back(make_pair(i,j));
    matrix[i][j] = 1;

    // 退出条件
    if(i == n-1 && j == m - 1){
        res = paths;
        return ;
    }
    
    // 向4个方向搜索：
    // 向上
    if(i-1 >= 0 && matrix[i-1][j] == 0){
        dfs(matrix, n, m, i-1, j, paths);
    }
    // 向下
    if(i+1 < n && matrix[i+1][j] == 0){
        dfs(matrix, n, m, i+1, j, paths);
    }
    // 向左
    if(j-1 >= 0 && matrix[i][j-1] == 0){
        dfs(matrix, n, m, i, j-1, paths);
    }
    // 向右
    if(j+1 < m  && matrix[i][j+1] == 0){
        dfs(matrix, n, m, i, j+1, paths);
    }

    // 回溯
    paths.pop_back();
    matrix[i][j] = 0;
}


int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> matrix(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> matrix[i][j];
        }
    }
    vector<pair<int,int>> paths; // 用于存放临时路径

    dfs(matrix, n, m, 0, 0, paths); //dfs遍历矩阵

    for(int i = 0; i < res.size(); i++) //输出路径
        cout << "(" << res[i].first << "," << res[i].second << ")" << endl;



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