题解 | 迷宫问题

#include <iostream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
using Point = pair<int, int>;
void backtrack(const vector<vector<int>>& grid, int i, int j, int h, int w,
               vector<Point>& path, vector<vector<bool>>& used, vector<Point>& ans) {
  //如果走到了终点，说明此时回溯过程容器装着的就是成功路劲（题目说了成功路径有且唯一）  
  if (i == h && j == w) {
        ans = path;
        return;
    }
    //上下左右各走一遍
    if ((i + 1) >= 0 && (i + 1) <= h && grid[i + 1][j] == 0 && !used[i + 1][j]) {
        //i-1仍在格子范围内，且没有障碍，且没有走过(i+1,j)
        path.push_back(Point(i + 1, j));
        used[i + 1][j] = true;
        backtrack(grid, i + 1, j, h, w, path, used, ans);
        path.pop_back();
        used[i + 1][j] = false;
    }
    if ((i - 1) >= 0 && (i - 1) <= h && grid[i - 1][j] == 0 && !used[i - 1][j]) {
        //i-1仍在格子范围内，且没有障碍，且没有走过(i-1,j)
        path.push_back(Point(i - 1, j));
        used[i - 1][j] = true;
        backtrack(grid, i - 1, j, h, w, path, used, ans);
        path.pop_back();
        used[i - 1][j] = false;
    }
    if ((j + 1) >= 0 && (j + 1) <= w && grid[i][j + 1] == 0 && !used[i][j + 1]) {
        //j+1仍在格子范围内，且没有障碍，且没有走过(i,j+1)
        path.push_back(Point(i, j + 1));
        used[i][j + 1] = true;
        backtrack(grid, i, j + 1, h, w, path, used, ans);
        path.pop_back();
        used[i][j + 1] = false;
    }
    if ((j - 1) >= 0 && (j - 1) <= w && grid[i][j - 1] == 0 && !used[i][j - 1]) {
        //j+1仍在格子范围内，且没有障碍，且没有走过(i,j-1)
        path.push_back(Point(i, j - 1));
        used[i][j - 1] = true;
        backtrack(grid, i, j - 1, h, w, path, used, ans);
        path.pop_back();
        used[i][j - 1] = false;
    }
}
void disp(const vector<Point>& path) {
    for (const auto& elem : path) {
        cout << "(" << elem.first << "," << elem.second << ")" << endl;
    }
}
int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<int>> grid(h, vector<int>(w, 0));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
        }
    }
    vector<Point> path;//回溯用的过程容器，每一个可能的路径路过都将由path承载
    vector<Point> ans;//找到成功路径以后将过程容器复制给ans
    vector<vector<bool>> used(h, vector<bool>(w, false));//状态数组，标记每一个点位是否走过；因为本题行走的方向是上下左右都可以走，所以回溯的时候有可能走到原来位置去，借助状态数组标记下一点是否是走过的点。如果是走过的点，我们不走这一步（if条件忽略）
    path.push_back(Point(0, 0));//第一个点进入回溯过程容器
    used[0][0] = true;//第一个点走过
    backtrack(grid, 0, 0, h - 1, w - 1, path, used, ans);
    disp(ans);//打印成功路劲
    return 0;
}
// 64 位输出请用 printf("%lld")

回溯算法，也叫DFS算法。每一个位置都是一个回溯点，都有上下左右四个选择，

回溯算法经典套路：

void backtrack(i，j){

1.终止条件

if(){

return;

}

2.遍历选择

2.1做选择

path.push（下一点）；

2.2做回溯

void backtrack(下一点)；

2.3撤销选择

path.pop（）；

}

以上套路框架细节上有一个需要注意的点：本题是可以四个方向任意走的，要避免往回走的情况，如果不避免，在某些回溯路径下出现反复横跳的情况，这样永远到不了终点，会陷入无限递归。