题解 | #迷宫问题# DFS回溯

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

bool dfs(vector<vector<int>>& res, vector<vector<int>>& maze, int i, int j) {
    int m = maze.size(), n = maze[0].size();
    // 索引不满足条件，返回false
    if (i < 0 || i >= m || j < 0 || j >= n || maze[i][j]) {
        return false;
    }
    // 将当前索引加入result数组
    res.push_back({i, j});
    // 将当前状态置为1，表示已访问过
    maze[i][j] = 1;
    // 访问到终点，返回true
    if (i == m - 1 && j == n - 1) {
        return true;
    }
    // 遍历四个方向，如果有一个方向为true，表示存在有效路径
    if (dfs(res, maze, i - 1, j) || dfs(res, maze, i + 1, j) ||
            dfs(res, maze, i, j - 1) || dfs(res, maze, i, j + 1)) {
        return true;
    }
    // 不存在有效路径，将当前索引弹出
    res.pop_back();
    // 状态置0，表示可以重新访问
    maze[i][j] = 0;
    return false;
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> maze(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> maze[i][j];
        }
    }
    vector<vector<int>> res;
    // dfs遍历
    dfs(res, maze, 0, 0);
    for (int i = 0; i < res.size(); i++) {
        cout << "(";
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j];
            if (j != res[i].size() - 1) {
                cout << ",";
            }
        }
        cout << ")" << endl;
    }
}
// 64 位输出请用 printf("%lld")