题解 | 迷宫问题

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

void dfs(int i, int j, int n, int m, vector<vector<int>>& best_path,
         vector<vector<int>>& temp_path, vector<vector<int>> maze) {
    //边界条件：（1）数组越界（2）“墙壁”或已走过
    if (i < 0 || i >= n || j < 0 || j >= m || maze[i][j] == 1) {
        return;
    }
    maze[i][j] = 1; //该位置已走过标记为1
    temp_path.push_back({i, j}); //将该位置加入路径
    if (i == n - 1 && j == m - 1) { //走到终点
        //多条路径时best_path记录最小的temp_path
        //if(temp_path.size()<best_path.size()||best_path.empty())
        //{
        //    best_path=temp_path;
        //}
//本题只有一条通路，所以当到达（n-1，m-1）时，让 best_path=temp_path即可
        best_path = temp_path;
    }
    dfs(i - 1, j, n, m, best_path, temp_path, maze); //上
    dfs(i + 1, j, n, m, best_path, temp_path, maze); //下
    dfs(i, j - 1, n, m, best_path, temp_path, maze); //左
    dfs(i, j + 1, n, m, best_path, temp_path, maze); //右
    maze[i][j] = 0; //该结点走不通时，恢复原场面
    temp_path.pop_back();//从路径中删除该节点
}

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<int>> maze(h, vector<int>(w));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> maze[i][j];
        }
    }
    vector<vector<int>> best_path;
    vector<vector<int>> temp_path;
    dfs(0, 0, h, w, best_path, temp_path, maze);
    for (vector<vector<int>>::iterator
            it = best_path.begin(); it != best_path.end(); it++) {
        cout << '(' << (*it)[0] << ',' << (*it)[1] << ')' << endl;
    }

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