题解 | #迷宫问题#

#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <array>
using namespace std;
static stack<array<int, 2>> road;
static bool dfs(vector<vector<int> >& maze, int i, int j) {
    int n = maze.size();
    int m = maze[0].size();
    if (i < 0 || i >= n || j < 0 || j >= m)
        return false;
    if (maze[i][j])
        return false;
    road.push({i, j});
    if (i == n - 1 && j == m - 1)
        return true;
    maze[i][j] = 1;
    bool ans = dfs(maze, i + 1, j) || dfs(maze, i - 1, j) || dfs(maze, i, j + 1) || dfs(maze, i, j - 1);
    maze[i][j] = 0;
    if (!ans)
        road.pop();
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > maze(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> maze[i][j];
    dfs(maze, 0, 0);
    vector<array<int, 2> > ans;
    while (!road.empty()) {
        auto tmp = road.top();
        ans.push_back(tmp);
        road.pop();
    }
    reverse(ans.begin(), ans.end());
    for (auto pos : ans)
        cout << '(' << pos[0] << ',' << pos[1] << ')' << '\n';

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

深度优先搜索，并将路径储存在栈中