LeetCode 题解工作台
网格传送门旅游
给你一个大小为 m x n 的二维字符网格 matrix ，用字符串数组表示，其中 matrix[i][j] 表示第 i 行和第 j 列处的单元格。每个单元格可以是以下几种字符之一： '.' 表示一个空单元格。 '#' 表示一个障碍物。 一个大写字母（ 'A' 到 'Z' ）表示一个传送门。 你从左…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以使用 0-1 BFS 来解决这个问题。我们从左上角单元格开始，使用双端队列来存储当前单元格的坐标。每次从队列中取出一个单元格，我们会检查它的四个相邻单元格，如果相邻单元格是空单元格且没有被访问过，我们就将它加入队列，并更新它的距离。 如果相邻单元格是一个传送门，我们就将它加入队列的前面，并更新它的距离。我们还需要维护一个字典来存储每个传送门的位置，以便在使用传送门时能够快速找到它们。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个大小为 m x n 的二维字符网格 matrix，用字符串数组表示，其中 matrix[i][j] 表示第 i 行和第 j 列处的单元格。每个单元格可以是以下几种字符之一：
'.'表示一个空单元格。'#'表示一个障碍物。- 一个大写字母（
'A'到'Z'）表示一个传送门。
你从左上角单元格 (0, 0) 出发，目标是到达右下角单元格 (m - 1, n - 1)。你可以从当前位置移动到相邻的单元格（上、下、左、右），移动后的单元格必须在网格边界内且不是障碍物。
如果你踏入一个包含传送门字母的单元格，并且你之前没有使用过该传送门字母，你可以立即传送到网格中另一个具有相同字母的单元格。这次传送不计入移动次数，但每个字母对应的传送门在旅程中 最多 只能使用一次。
返回到达右下角单元格所需的 最少 移动次数。如果无法到达目的地，则返回 -1。
示例 1：
输入： matrix = ["A..",".A.","..."]
输出： 2
解释：
- 在第一次移动之前，从
(0, 0)传送到(1, 1)。 - 第一次移动，从
(1, 1)移动到(1, 2)。 - 第二次移动，从
(1, 2)移动到(2, 2)。
示例 2：
输入： matrix = [".#...",".#.#.",".#.#.","...#."]
输出： 13
解释：
提示：
1 <= m == matrix.length <= 1031 <= n == matrix[i].length <= 103matrix[i][j]是'#'、'.'或一个大写英文字母。matrix[0][0]不是障碍物。
解题思路
方法一：0-1 BFS
我们可以使用 0-1 BFS 来解决这个问题。我们从左上角单元格开始，使用双端队列来存储当前单元格的坐标。每次从队列中取出一个单元格，我们会检查它的四个相邻单元格，如果相邻单元格是空单元格且没有被访问过，我们就将它加入队列，并更新它的距离。
如果相邻单元格是一个传送门，我们就将它加入队列的前面，并更新它的距离。我们还需要维护一个字典来存储每个传送门的位置，以便在使用传送门时能够快速找到它们。
我们还需要一个二维数组来存储每个单元格的距离，初始值为无穷大。我们将起点的距离设置为 0，然后开始 BFS。
在 BFS 的过程中，我们会检查每个单元格是否是终点，如果是，就返回它的距离。如果队列为空，说明无法到达终点，返回 -1。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
class Solution:
def minMoves(self, matrix: List[str]) -> int:
m, n = len(matrix), len(matrix[0])
g = defaultdict(list)
for i, row in enumerate(matrix):
for j, c in enumerate(row):
if c.isalpha():
g[c].append((i, j))
dirs = (-1, 0, 1, 0, -1)
dist = [[inf] * n for _ in range(m)]
dist[0][0] = 0
q = deque([(0, 0)])
while q:
i, j = q.popleft()
d = dist[i][j]
if i == m - 1 and j == n - 1:
return d
c = matrix[i][j]
if c in g:
for x, y in g[c]:
if d < dist[x][y]:
dist[x][y] = d
q.appendleft((x, y))
del g[c]
for a, b in pairwise(dirs):
x, y = i + a, j + b
if (
0 <= x < m
and 0 <= y < n
and matrix[x][y] != "#"
and d + 1 < dist[x][y]
):
dist[x][y] = d + 1
q.append((x, y))
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m _n + total portal connections), as each cell is processed once and each portal super-node is expanded once. Space complexity is O(m_ n + number of portals) to store visited states and portal mappings. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Watch for repeatedly scanning the entire matrix for portals, which increases runtime.
- question_mark
Verify BFS handles one-time portal usage correctly to avoid overcounting moves.
- question_mark
Consider edge cases where portals lead to dead ends or the target is unreachable.
常见陷阱
外企场景- error
Failing to mark portals as used after first teleport can cause infinite loops.
- error
Forgetting to check grid boundaries before moving results in index errors.
- error
Assuming teleportation counts as a move, which inflates the path length incorrectly.
进阶变体
外企场景- arrow_right_alt
Allow portals to be used multiple times, turning the problem into standard multi-source BFS.
- arrow_right_alt
Restrict movement to only horizontal or vertical directions but no diagonal, increasing path constraints.
- arrow_right_alt
Introduce weighted moves where teleportation has a cost greater than zero, changing BFS to Dijkstra.