题解 | #迷宫问题# C++ 回溯

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

void dfs(vector<vector<int>>& puzzle,
         int i, int j, vector<pair<int, int>>& path,
         vector<pair<int, int>>& res) {
    int m = (int)puzzle.size();
    int n = (int)puzzle[0].size();
    if (i < 0 || i >= m || j < 0 || j >= n || puzzle[i][j] == 1) {
        return;
    }
    puzzle[i][j] = 1; // 访问过
    path.emplace_back(i, j);
    if ((i == m - 1 && j == n - 1)) {
        res.assign(path.begin(), path.end());
        return;
    }
    vector<pair<int, int>> dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    for (const auto& p : dir) {
        int newi = p.first + i;
        int newj = p.second + j;
        dfs(puzzle, newi, newj, path,res);
    }
    puzzle[i][j] = 0;
    path.pop_back();
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> puzzle(m, vector<int>(n, 0));
    vector<pair<int, int>> path;
    vector<pair<int, int>> res;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> puzzle[i][j];
        }
    }

    dfs(puzzle, 0, 0, path, res);
    for (auto& p : res) {
        cout << "(" << p.first << "," << p.second << ")" << endl;
    }
    return 0;
}