标签:
难度: Hard
标签:
难度: Hard
运行时间: 701 ms
内存: 17.1 MB
from collections import deque from heapq import heappush, heappop class Solution: def challengeOfTheKeeper(self, maze: List[str]) -> int: move = [-1, 0, 1, 0, -1] m = len(maze) n = len(maze[0]) arr = [[-1]*n for _ in range(m)] for i in range(m): for j in range(n): if maze[i][j] == "#": arr[i][j] = -2 elif maze[i][j] == "S": start = (i, j) elif maze[i][j] == "T": end = (i, j) arr[i][j] = 0 q = deque() q.append(end) step = 1 while q: size = len(q) for _ in range(size): x, y = q.popleft() for i in range(4): x2 = x + move[i] y2 = y + move[i+1] if 0 <= x2 < m and 0 <= y2 < n and arr[x2][y2] == -1: arr[x2][y2] = step q.append((x2, y2)) step += 1 if arr[start[0]][start[1]] == -1: return -1 minHeap = [(0, start[0], start[1])] vis = [[False]*n for _ in range(m)] res = 0 while minHeap: val, x, y = heappop(minHeap) if vis[x][y]: continue vis[x][y] = True res = max(res, val) for i in range(4): x2 = x + move[i] y2 = y + move[i+1] if x2 == end[0] and y2 == end[1]: return res if 0 <= x2 < m and 0 <= y2 < n and arr[x2][y2] != -2 and not vis[x2][y2]: if arr[m-1-x2][y2] == -1 or arr[x2][n-1-y2] == -1: continue maxv = max(arr[m-1-x2][y2], arr[x2][n-1-y2]) if maxv == -2: heappush(minHeap, (0, x2, y2)) else: heappush(minHeap, (maxv, x2, y2)) return -1
该题解采用了两步广度优先搜索(BFS)和优先队列(最小堆)的混合策略。首先,从魔法水晶位置(终点T)开始第一次BFS,遍历迷宫以计算每个空地到魔法水晶的最短步数。这些步数储存在二维数组arr中,其中墙壁的位置被标记为-2。接下来,从小扣的起始位置(起点S)开始,使用优先队列进行另一次搜索,以考虑魔法卷轴的使用。搜索时,每次移动到一个新位置时,都会计算如果在此使用魔法卷轴的话,被传送到镜像位置后到达终点T的最短步数,并更新到达终点T的最短距离。
时间复杂度: O((m*n) * log(m*n))
空间复杂度: O(m*n)
from collections import deque from heapq import heappush, heappop class Solution: def challengeOfTheKeeper(self, maze: List[str]) -> int: move = [-1, 0, 1, 0, -1] # 移动方向(上、右、下、左) m, n = len(maze), len(maze[0]) # 迷宫的尺寸 arr = [[-1]*n for _ in range(m)] # 用于存储到达T的最短步数,初始化为-1 for i in range(m): # 遍历迷宫 for j in range(n): if maze[i][j] == '#': # 标记墙壁 arr[i][j] = -2 elif maze[i][j] == 'S': # 记录起始位置 start = (i, j) elif maze[i][j] == 'T': # 记录终点位置,初始化步数为0 end = (i, j) arr[i][j] = 0 q = deque([end]) # 从终点开始第一次BFS step = 1 while q: # 对迷宫中所有点计算到T的最短距离 for _ in range(len(q)): x, y = q.popleft() for i in range(4): # 对于每个点,考虑四个方向的移动 x2, y2 = x + move[i], y + move[i+1] if 0 <= x2 < m and 0 <= y2 < n and arr[x2][y2] == -1: # 可以移动的条件 arr[x2][y2] = step # 更新步数 q.append((x2, y2)) # 添加到队列中 step += 1 if arr[start[0]][start[1]] == -1: # 如果起始位置无法到达终点 return -1 minHeap = [(0, start[0], start[1])] # 从起点开始,考虑魔法卷轴的使用 vis = [[False]*n for _ in range(m)] # 记录已访问的点 res = 0 while minHeap: # 使用优先队列进行搜索 val, x, y = heappop(minHeap) if vis[x][y]: # 如果已访问,则跳过 continue vis[x][y] = True res = max(res, val) # 更新到达终点的最短步数 for i in range(4): x2, y2 = x + move[i], y + move[i+1] if x2 == end[0] and y2 == end[1]: # 如果达到终点 return res if 0 <= x2 < m and 0 <= y2 < n and arr[x2][y2] != -2 and not vis[x2][y2]: # 检查移动是否有效 if arr[m-1-x2][y2] == -1 or arr[x2][n-1-y2] == -1: # 魔法卷轴传送位置是否有效 continue maxv = max(arr[m-1-x2][y2], arr[x2][n-1-y2]) # 选择最佳传送位置的步数 if maxv == -2: # 如果传送后仍是墙壁 heappush(minHeap, (0, x2, y2)) else: heappush(minHeap, (maxv, x2, y2)) return -1 # 如果无法到达终点,返回-1
在第一次BFS中,数组初始化为-1主要用于区分哪些位置尚未被访问过。由于BFS是用来计算从终点T到迷宫中每个可达点的最短路径,初始化为-1可以方便地检查某个位置是否已被计算过步数。一旦某个位置的步数被计算(即从-1变为具体步数),就表明该位置已经被访问过。而对于墙壁位置使用-2进行标记,则是为了在后续处理中能够快速识别出哪些位置是墙壁,即不可通过的区域。
在第二次使用优先队列的搜索中,代码利用了魔法卷轴的能力来计算镜像位置。具体的镜像位置计算方法是:对于当前位置 (x, y),其在水平方向的镜像位置是 (m-1-x, y) ,而在垂直方向的镜像位置是 (x, n-1-y),其中m和n分别是迷宫的行数和列数。为了确保镜像位置不落在墙壁上,代码在将新位置添加到优先队列之前,会检查该位置在arr数组中的值是否为-2。如果是-2,则表示该位置是墙壁,因此不会选择该位置为有效的传送目标。
这一逻辑是通过检查第一次BFS完成后,起始位置S在arr数组中的值来实现的。在进行第一次BFS后,如果起始位置S在arr中的值仍然是-1,这表示从终点T到起始位置S没有有效的路径。这种情况下代码直接返回-1,表示无法到达终点。这一逻辑的实现位于代码中这样一行:`if arr[start[0]][start[1]] == -1: return -1`。这行代码检查起始位置S在数组arr中的值,如果为-1,则返回-1表示无法完成任务。