题解 | #迷宫问题#

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

vector<pair<int, int>> result;

void dfs(vector<vector<int>>& maze, int i, int j,
         vector<pair<int, int>>& road) {
    //向路径加入元素
    road.push_back(pair<int, int>(i, j));
    maze[i][j] = 1;//封锁回头路
    // 终止条件:走到终点
    if (i == maze.size() - 1 && j == maze[i].size() - 1) {
        result = road;
        return;
    }

    if (i + 1 <= maze.size() - 1 && maze[i + 1][j] == 0) {
        //向下寻找路径
        dfs(maze, i + 1, j, road);
    }
    if (j + 1 <= maze[i].size() - 1 && maze[i][j + 1] == 0) {
        //向右寻找路径
        dfs(maze, i, j + 1, road);
    }
    if (i - 1 >= 0 && maze[i - 1][j] == 0) {
        //向左寻找路径
        dfs(maze, i - 1, j, road);
    }
    if (j - 1 >= 0 && maze[i][j - 1] == 0) {
        //向上寻找路径
        dfs(maze, i, j - 1, road);
    }
    //回溯
    road.pop_back();
    maze[i][j] = 0;

}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> maze(n, vector<int>(m, 0));
    vector<pair<int, int>> road;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
        }
    }

    dfs(maze, 0, 0, road);

    for (auto& r : result) {
        cout << "(" << r.first << "," << r.second << ")" << endl;
    }
}

解题时我使用了回溯的知识；

要使用回溯有几个要点

退出条件（递归到地图底边）把此刻的路径传到main函数中再输出即可

接下来要遍历的集合（上下左右寻找）

回溯代码（将路径和地图重置到遍历到此节点之前的状态）