传送卷轴

标签:

难度: Hard

随着不断的深入，小扣来到了守护者之森寻找的魔法水晶。首先，他必须先通过守护者的考验。 考验的区域是一个正方形的迷宫，`maze[i][j]` 表示在迷宫 `i` 行 `j` 列的地形： - 若为 `.` ，表示可以到达的空地； - 若为 `#` ，表示不可到达的墙壁； - 若为 `S` ，表示小扣的初始位置； - 若为 `T` ，表示魔法水晶的位置。 小扣每次可以向 上、下、左、右 相邻的位置移动一格。而守护者拥有一份「传送魔法卷轴」，使用规则如下： - 魔法需要在小扣位于 **空地** 时才能释放，发动后卷轴消失；； - 发动后，小扣会被传送到水平或者竖直的镜像位置，且目标位置不得为墙壁(如下图所示)； ![image.png](https://pic.leetcode.cn/1681789509-wTekFu-image.png){:width=400px} 在使用卷轴后，小扣将被「附加负面效果」，因此小扣需要尽可能缩短传送后到达魔法水晶的距离。而守护者的目标是阻止小扣到达魔法水晶的位置；如果无法阻止，则尽可能 **增加** 小扣传送后到达魔法水晶的距离。 假设小扣和守护者都按最优策略行事，返回小扣需要在 「附加负面效果」的情况下 **最少** 移动多少次才能到达魔法水晶。如果无法到达，返回 `-1`。 **注意：** - 守护者可以不使用卷轴； - 传送后的镜像位置可能与原位置相同。 **示例 1：** >输入：`maze = [".....","##S..","...#.","T.#..","###.."]` > >输出：`7` > >解释：如下图所示： >守护者释放魔法的两个最佳的位置为 [2,0] 或 [3,1]： >若小扣经过 [2,0]，守护者在该位置释放魔法， >小扣被传送至 [2,4] 处且加上负面效果，此时小扣还需要移动 7 次才能到达魔法水晶； >若小扣经过 [3,1]，守护者在该位置释放魔法， >小扣被传送至 [3,3] 处且加上负面效果，此时小扣还需要移动 9 次才能到达魔法水晶； >因此小扣负面效果下最少需要移动 7 次才能到达魔法水晶。 ![image.png](https://pic.leetcode.cn/1681714676-gksEMT-image.png){:width=300px} **示例 2：** >输入：`maze = [".#..","..##",".#S.",".#.T"]` > >输出：`-1` > >解释：如下图所示。 >若小扣向下移动至 [3,2]，守护者使其传送至 [0,2]，小扣将无法到达魔法水晶； >若小扣向右移动至 [2,3]，守护者使其传送至 [2,0]，小扣将无法到达魔法水晶； ![image.png](https://pic.leetcode.cn/1681714693-LsxKAh-image.png){:width=300px} **示例 3：** >输入：`maze = ["S###.","..###","#..##","##..#","###.T"]` > >输出：`5` > >解释：如下图所示： >守护者需要小扣在空地才能释放，因此初始无法将其从 [0,0] 传送至 [0,4]; >当小扣移动至 [2,1] 时，释放卷轴将其传送至水平方向的镜像位置 [2,1]（为原位置） >而后小扣需要移动 5 次到达魔法水晶 ![image.png](https://pic.leetcode.cn/1681800985-KrSdru-image.png){:width=300px} **提示：** - `4 <= maze.length == maze[i].length <= 200` - `maze[i][j]` 仅包含 `"."`、`"#"`、`"S"`、`"T"`

Submission

运行时间: 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

Explain

该题解采用了两步广度优先搜索（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

Explore

在第一次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表示无法完成任务。