众所周知,出题人没玩过《双人成行》,于是给出了如下经典二人协作版迷宫问题。孤岛被划分为 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 3 2 2 @.@ #.. @.@
2
1 3 1 2 ..@
3
3 1 2 1 # . @
-1
考点:广度优先搜索(BFS)
数据规模 n ≤ 2000 | 限制 1 秒 / 256MB | 标准输入输出
推荐方向:广度优先搜索(BFS)
按层扩散搜索,无权图上第一次到达即最短路。
思路框架(广度优先搜索(BFS) 通法 · 非本题专属)
实现要点:标记访问必须在入队时做,不能在出队时做,否则会重复入队甚至超时。
复杂度:时间 O(V+E) | 空间 O(V)
该范式的通法易错点
对照本题
样例 1:输入 3 3 2 2 / @.@ / #.. / @.@ → 输出 2
你可以先往上后往左到达(1,1)传送门
另外一个时空的你会先下后右到达(3,3)传送门
样例 2:输入 3 1 2 1 / # / . / @ → 输出 -1
显然,谁都不想走到陷阱那 ...
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:华为机试编程模拟题8;2024年秋招-蔚来汽车-后端岗笔试。