使用 广度优先搜索(BFS) 求解迷宫最短路径问题。BFS 自然保证第一次到达某状态时即为最短步数。
预处理 扫描整个地图,记录:
在一个 m 行 n 列的二维网格迷宫中,每个格子都有明确的类型。0 表示可以通行的空地,1 表示无法进入的墙壁,S 表示起点,E 表示终点。迷宫中还可能存在成对出现的虫洞,它们用 2 表示。当移动到某个虫洞格时,可以立即被送到与之配对的另一个虫洞格,传送本身不消耗额外步数。
你只能沿上下左右四个方向移动,每一步从当前格进入相邻格。移动时不能越过网格边界,也不能进入墙壁格。需要计算从起点 S 到终点 E 的最少移动步数。如果不存在可行路径,则结果为 -1。
约束条件: 迷宫的行数 m 和列数 n 满足 1≤m,n≤50。
虫洞的数量恰好为2 或 0 。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册