题解 | #迷宫问题#

#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> pathList;
using namespace std;
bool search(const std::vector<std::vector<bool>>& maze, int m, int n, int i,
            int j, std::vector<std::vector<bool>>& visited) {
    visited[i][j] = true;
    if (i == m - 1 && j == n - 1) {
        pathList.push_back("(" + std::to_string(i) + "," + std::to_string(j) + ")");
        return true;
    }
    int newI, newJ;
    bool accessable;
    // go up
    if (i - 1 >= 0 && maze[i - 1][j] && !visited[i - 1][j]) {
        newI = i - 1;
        newJ = j;
        accessable = search(maze, m, n, newI, newJ, visited);
        if (accessable) {
            pathList.push_back("(" + std::to_string(i) + "," + std::to_string(j) + ")");
            return true;
        }
    }
    // go down
    if (i + 1 < m && maze[i + 1][j] && !visited[i + 1][j]) {
        newI = i + 1;
        newJ = j;
        accessable = search(maze, m, n, newI, newJ, visited);
        if (accessable) {
            pathList.push_back("(" + std::to_string(i) + "," + std::to_string(j) + ")");
            return true;
        }
    }
    // go left
    if (j - 1 >= 0 && maze[i][j - 1] && !visited[i][j - 1]) {
        newI = i;
        newJ = j - 1;
        accessable = search(maze, m, n, newI, newJ, visited);
        if (accessable) {
            pathList.push_back("(" + std::to_string(i) + "," + std::to_string(j) + ")");
            return true;
        }
    }
    // go right
    if (j + 1 < n && maze[i][j + 1] && !visited[i][j + 1]) {
        newI = i;
        newJ = j + 1;
        accessable = search(maze, m, n, newI, newJ, visited);
        if (accessable) {
            pathList.push_back("(" + std::to_string(i) + "," + std::to_string(j) + ")");
            return true;
        }
    }
    return false;
}

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

    std::vector<std::vector<bool>> maze(m, std::vector<bool>(n));
    std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int temp;
            std::cin >> temp;
            maze[i][j] = (temp == 0);
        }
    }

    search(maze, m, n, 0, 0, visited);

    for (auto x = pathList.end()-1;x>=pathList.begin();x--) {
        cout<<*x<<endl;
    }

    return 0;
}