题解 | #迷宫问题#

// 考虑没有路径和最短路径
#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> best_path;

bool dfs(vector<vector<int>>& maze, vector<pair<int, int>>& recode, int x, int y) {
    if (x == maze.size() - 1 && y == maze[0].size() - 1) {
        recode.push_back(pair<int, int>({x, y}));
        if (best_path.empty() || best_path.size() > recode.size()) {
            best_path = recode;
        }
        return true;
    }
    else if (x < 0 || x == maze.size() || y < 0 || y == maze[0].size() || maze[x][y] == 1) {
        return false;
    }

    maze[x][y] = 1;
    recode.push_back(pair<int, int>({x, y}));
    bool d1 = dfs(maze, recode, x - 1, y);
    bool d2 = dfs(maze, recode, x + 1, y);
    bool d3 = dfs(maze, recode, x, y - 1);
    bool d4 = dfs(maze, recode, x, y + 1);

    // 深度搜索的回溯是回到另一个选项，如d2经过一番搜索结束，要进行d3搜索回溯到d2未进行前
    maze[x][y] = 0;
    recode.pop_back();
    if (d1 || d2 || d3 || d4) {
        return true;
    }
    else {
        return false;
    }

}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> maze(n, vector<int>(m, 0));
    for (auto& i : maze) {
        for (auto& j : i) {
            cin >> j;
        }
    }
    vector<pair<int, int>> recode;
    if(dfs(maze, recode, 0, 0)) {
        for (const auto& it : best_path) {
            cout << "(" << it.first << "," << it.second <<")" << endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")