华为 · 广度优先搜索(BFS) · 算法编程题
华为 广度优先搜索(BFS) n ≤ 20 时限 1 秒 / 256 MB

题目描述

小红在一个 n × m 的网格遗迹中移动。网格含义如下：
- `0`：可通行空地；
- `1`：障碍物；
- `2`：起点；
- `3`：宝箱；
- `4` 到 `9`：对应编号的碎片。
小红每次可以向上、下、左、右移动一格，耗时为 1 。她必须按编号从小到大收集网格中的全部碎片，编号可以不连续；同一编号可能出现多次，必须全部收集完后才能进入更大编号的碎片格。移动经过碎片格即视为收集该碎片，收集完全部碎片后才能进入宝箱。
求从起点出发、收集所有碎片并到达宝箱的最短耗时。若无法完成，输出 -1 。

输入输出

输入描述
第一行输入两个整数 n,m 。
接下来 n 行，每行输入 m 个整数，描述网格。
保证 1 ≤ n,m ≤ 20 ；恰有一个起点和一个宝箱；每个碎片编号最多出现 3 次。
输出描述
输出最短总耗时；若无法完成，输出 -1 。

样例共 2 组

样例 1 · 依次到达编号 4、5 的碎片，再进入宝箱。
输入
4 5
2 0 0 0 0
1 0 4 0 0
1 0 1 5 0
1 0 1 1 3
输出
7
样例 2 · 需要依次收集 4、5、6 号碎片，并绕开障碍物。
输入
5 5
0 2 0 0 0
0 1 0 4 0
0 1 0 1 5
0 1 0 6 1
0 1 0 0 3
输出
13

算法解析依据充分

考点：广度优先搜索(BFS)

数据规模 n ≤ 20 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 20，m ≤ 20
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：广度优先搜索(BFS)

本题切入点

按碎片编号顺序逐段 BFS：从当前位置 BFS 找到同编号所有碎片格的最短路（多目标取最小），再走向宝箱；n,m≤20 规模下逐段 BFS 完全可行，无法完成输出 −1。

按层扩散搜索，无权图上第一次到达即最短路。

思路框架（广度优先搜索(BFS) 通法 · 非本题专属）

  1. 起点入队并标记已访问。
  2. 每次取队首，把它的所有未访问邻居入队并记录步数。
  3. 第一次访问到目标时，步数即为最少步数。
  4. 网格类题目通常有 4（或 8）个方向，用方向数组统一处理。

实现要点：标记访问必须在入队时做，不能在出队时做，否则会重复入队甚至超时。

复杂度：时间 O(V+E) ｜ 空间 O(V)

该范式的通法易错点

  • 出队才标记访问导致 MLE/TLE。
  • 网格边界没判，越界访问。
  • 多源 BFS 时只把第一个起点入队。

对照本题

  • 数据规模 n ≤ 20，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。

样例解读

样例 1：输入 4 5 / 2 0 0 0 0 / 1 0 4 0 0 / 1 0 1 5 0 / 1 0 1 1 3 → 输出 7

依次到达编号 4、5 的碎片，再进入宝箱。

样例 2：输入 5 5 / 0 2 0 0 0 / 0 1 0 4 0 / 0 1 0 1 5 / 0 1 0 6 1 / 0 1 0 0 3 → 输出 13

需要依次收集 4、5、6 号碎片，并绕开障碍物。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2026年-华为-05月27号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解