Walking Through the Maze

走迷宫

给定一个 n × m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁

最初，有一个人位于左上角 (1, 1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置

请问，该人从左上角移动至右下角 (n, m) 处，至少需要移动多少次

数据保证 (1, 1) 处和 (n, m) 处的数字为 0，且一定至少存在一条通路

输入格式

第一行包含两个整数 n 和 m
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数

数据范围

1

1 ≤ n, m ≤ 100

输入样例

输出样例

1

8

分析

每次在 上下左右 四个方向上移动 1 步，抽象为无权图的最短路径问题

BFS（广度优先搜索） 可以保证 最先到达终点的一定是最短路径

变量定义
- g[N][N] 记录迷宫（0 可通行，1 代表墙）
- d[N][N] 记录 从起点 (0, 0) 到当前点 (i, j) 需要走的步数，初始值设为 -1 代表未访问
- q[N*N] 是 BFS 队列（数组模拟队列），用于存储待访问的坐标点
BFS 过程
- (0, 0) 开始，将 d[0][0] 设为 0 并入队
- 依次处理队列中的每个点 (x, y)：
  - 遍历四个方向 dx[i], dy[i]，尝试移动到 (a, b) = (x + dx[i], y + dy[i])
  - 如果 (a, b) 没超出边界、未访问、且 g[a][b] == 0（可通行），则：
    - 记录 d[a][b] = d[x][y] + 1
    - 将 (a, b) 入队，继续搜索
- 终点 (n - 1, m - 1) 的 d 值即为最短路径

时间复杂度

每个格子最多入队一次，BFS 遍历所有点的时间复杂度为 O(nm)

空间复杂度

主要由 d 数组和队列 q 组成，空间复杂度为 O(nm)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


#include <cstring>
#include <iostream>

const int N = 110;
int g[N][N];  // 迷宫
int d[N][N];  // 记录最短路径步数

int main()
{
  int n, m;
  std::cin >> n >> m;

  // 读取迷宫
  for (int i = 0; i < n; ++ i)
    for (int j = 0; j < m; ++ j)
      std::cin >> g[i][j];

  std::memset(d, -1, sizeof d);  // -1 表示未访问
  d[0][0] = 0;  // 起点步数设为 0

  using PII = std::pair<int, int>;
  PII q[N * N];  // BFS 队列
  int hh = 0, tt = 0;
  q[0] = {0, 0};  // 起点入队

  // 方向数组：右、下、左、上
  int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

  // BFS 遍历
  while (hh <= tt)
  {
    auto [x, y] = q[hh ++ ];  // 取队头元素

    for (int i = 0; i < 4; ++ i)
    {
      int a = x + dx[i], b = y + dy[i];
      if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 0 && d[a][b] == -1)
      {
        q[ ++ tt] = {a, b};  // 加入队列
        d[a][b] = d[x][y] + 1;  // 记录步数
      }
    }
  }

  // 输出终点的最短步数
  std::cout << d[n - 1][m - 1] << '\n';

  return 0;
}