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

题目描述

给定一个 n × m 的迷宫，迷宫由 "#" 与"." 两种字符组成。其中 "#" 代表障碍物，"." 表示空地。迷宫中还有一个起点 "S" 和一个终点 "E" ，它们都可以视为空地。
由于近期迷宫发生了塌方，导致起点和终点之间可能并不连通。幸运的是，你拥有一种超能力——在迷宫中移动时（移动方向为上、下、左、右四个方向之一），可以在当前位置朝任一方向（上、下、左、右四个方向之一）释放激光。激光能够清除该方向上所有的障碍物，并且这种超能力至多只能使用一次。
现在，你需要判断是否能利用这种超能力成功从起点到达终点。

输入输出

输入描述
第一行给定两个整数 n,m(2 ≤ n,m ≤ 1000) ，分别表示迷宫的行数和列数。
下面 n 行，每行 m 个字符，描述迷宫的具体布局。字符只包含 "#"、"."、"S" 和 "E"，并且起点与终点有且仅有一个。
输出描述
能够到达终点输出 YES ；否则输出 NO 。

样例共 3 组

样例 1
输入
4 5
.####
S####
.####
.E###
输出
YES
样例 2 · 显然可以从起点出发，到达 (1,2) 处并向下方使用超能力，此时可以从起点到达终点。
输入
4 5
..###
S####
#####
##.E#
输出
YES
样例 3
输入
4 5
..###
S####
#####
###E#
输出
NO

算法解析依据充分

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

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

题目画像

  • 数据规模：n ≤ 1e3，m ≤ 1e3
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

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

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。

样例解读

样例 1：输入 4 5 / ..### / S#### / ##### / ##.E# → 输出 YES

显然可以从起点出发，到达 (1,2) 处并向下方使用超能力，此时可以从起点到达终点。

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

本题来源：华为机试编程模拟题4。

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