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

题目描述

众所周知,出题人没玩过《双人成行》,于是给出了如下经典二人协作版迷宫问题。孤岛被划分为 n × m 个方格,按行从上到下、列从左到右编号为 (1,1) 至 (n,m) 。地图上的地形分为三种:
平地(`.`)——可以自由经过;
陷阱(`#`)——踩上去立即死亡;
传送门(`@`)——一旦进入便会立刻离开孤岛。
你与来自平行时空的另一个"你"最初同时位于坐标 (x,y) 的同一块平地。两人每次必须同时行动,且朝相反方向各移动一步,即:
如果你选择向上,则另一个你必须向下;
如果你选择向左,则另一个你必须向右,依此类推。
在任何时刻,若有人走出边界或踏入陷阱,游戏立即失败;若有人到达传送门,则他会立刻离开并不再返回,之后剩下的那个人可以单独自由移动(不再受"相反方向"限制)。
请判断是否存在一条合法的移动序列,使得两个人都能成功离开孤岛;若存在,请输出最短所需步数,否则输出 -1 。

输入输出

输入描述
输入包含 n+1 行:
第一行输入四个整数 n,m,x,y(1≤ n,m≤ 2×10^3;1≤ x≤ n;1≤ y≤ m) ;
接下来 n 行,第 i 行输入一个长度为 m 的字符串 s_i ,仅由 `.`、`#`、`@` 组成,描述第 i 行的地形。
保证起点 (x,y) 处为平地。
输出描述
若存在可行方案,输出最短移动步数;否则输出 -1 。

样例共 3 组

样例 1 · 你可以先往上后往左到达(1,1)传送门 另外一个时空的你会先下后右到达(3,3)传送门
输入
3 3 2 2
@.@
#..
@.@
输出
2
样例 2
输入
1 3 1 2
..@
输出
3
样例 3 · 显然,谁都不想走到陷阱那 ...
输入
3 1 2 1
#
.
@
输出
-1

算法解析依据充分

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

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

题目画像

  • 数据规模:n ≤ 2000,m ≤ 2000
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

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

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

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

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

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

复杂度:时间 O(V+E) | 空间 O(V)

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 2000,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。

样例解读

样例 1:输入 3 3 2 2 / @.@ / #.. / @.@ → 输出 2

你可以先往上后往左到达(1,1)传送门

另外一个时空的你会先下后右到达(3,3)传送门

样例 2:输入 3 1 2 1 / # / . / @ → 输出 -1

显然,谁都不想走到陷阱那 ...

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

本题来源:华为机试编程模拟题8;2024年秋招-蔚来汽车-后端岗笔试。

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