题解 | #迷宫问题#

#include <iostream>
#include <vector>

using namespace std;
struct Point {
  int x = 0;
  int y = 0;
};
std::vector<Point> path_tmp;
std::vector<Point> path;
bool found = false;
int n = 0;
int m = 0;
// maze是原始的迷宫，status是记录每个点是否遍历过, (x, y)代表当前点
void dfs(const std::vector<std::vector<int>>& maze, int x, int y, std::vector<std::vector<int>>& status) {
  Point cur;
  cur.x = x;
  cur.y = y;
  path_tmp.push_back(cur);
  status[x][y] = 1;

  // 因为只有一条路径, 到达右下角即可停止遍历
  if ((x == n - 1 && y == m - 1)) {
    path = path_tmp;
    return;
  }
  // 往上遍历
  if (x > 0 && maze[x - 1][y] == 0 && status[x - 1][y] == 0) {
    dfs(maze, x - 1, y, status);
  }
  // 往下遍历
  if (x + 1 < n && maze[x + 1][y] == 0 && status[x + 1][y] == 0) {
    dfs(maze, x + 1, y, status);
  }
  // 往左遍历
  if (y > 0 && maze[x][y - 1] == 0 && status[x][y - 1] == 0) {
    dfs(maze, x, y - 1, status);
  }
  // 往右遍历
  if (y + 1 < m && maze[x][y + 1] == 0 && status[x][y + 1] == 0) {
    dfs(maze, x, y + 1, status);
  }
  // 四个方向都不行, 回退到上个点
  path_tmp.pop_back();
  status[x][y] = 0;
}

int main() {
  // 读取迷宫行数、列数
  cin >> n >> m;
  cin.ignore();

  // 读取迷宫每个点
  std::vector<std::vector<int>> maze(n, std::vector<int>(m, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> maze[i][j];
    }
    cin.ignore();
  }

  // 0代表未遍历过
  std::vector<std::vector<int>> status(n, std::vector<int>(m, 0));
  // dfs遍历，寻找路径
  dfs(maze, 0, 0, status);
  for (const auto& p : path) {
    std::cout << "(" << p.x << "," << p.y << ")" << std::endl;
  }

  return 0;
}