传送卷轴
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 701 ms, 内存: 17.1 MB
解释
方法:
该题解采用了两步广度优先搜索（BFS）和优先队列（最小堆）的混合策略。首先，从魔法水晶位置（终点T）开始第一次BFS，遍历迷宫以计算每个空地到魔法水晶的最短步数。这些步数储存在二维数组arr中，其中墙壁的位置被标记为-2。接下来，从小扣的起始位置（起点S）开始，使用优先队列进行另一次搜索，以考虑魔法卷轴的使用。搜索时，每次移动到一个新位置时，都会计算如果在此使用魔法卷轴的话，被传送到镜像位置后到达终点T的最短步数，并更新到达终点T的最短距离。
时间复杂度:
O((m*n) * log(m*n))
空间复杂度:
O(m*n)
代码细节讲解
🦆
在进行第一次BFS时，对于墙壁位置使用了-2进行标记，那么在数组中初始化为-1是出于什么考虑？
▷🦆
第二次搜索时，优先队列考虑了魔法卷轴的使用，但具体是如何计算镜像位置的，以及如何保证这一步的镜像位置不会落在墙壁上？
▷🦆
代码中提到如果起始位置S无法到达终点T就返回-1，这是如何通过第一次BFS实现的？具体是哪一部分代码实现这一逻辑？
▷