M3552.网络传送门旅游

bfs, https://leetcode.cn/problems/grid-teleportation-traversal/

给你一个大小为 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 <= 10^3
1 <= n == matrix[i].length <= 10^3
matrix[i][j] 是 '#'、'.' 或一个大写英文字母。
matrix[0][0] 不是障碍物。

下面的方法用 0-1 BFS（双端队列）来精确处理「普通移动（权重 1）」和「传送（权重 0）」两种边，保证任何情况下都能找到最短步数，并且仅 $O (m n)$ 内存：

python

from collections import deque, defaultdict
from typing import List

class Solution:
    def minMoves(self, matrix: List[str]) -> int:
        m, n = len(matrix), len(matrix[0])
        # 4 个方向向量
        dirs = [(-1,0),(1,0),(0,-1),(0,1)]
        
        # 1) 收集每个字母的传送门位置
        portal_map = defaultdict(list)
        for i in range(m):
            for j in range(n):
                c = matrix[i][j]
                if 'A' <= c <= 'Z':
                    portal_map[c].append((i, j))
        
        # 2) dist[i][j] = 到 (i,j) 的最短步数。初始化为无穷大
        INF = 10**18
        dist = [[INF]*n for _ in range(m)]
        dist[0][0] = 0
        
        dq = deque()
        dq.append((0, 0))
        
        while dq:
            x, y = dq.popleft()
            d = dist[x][y]
            # 一旦到达终点就可以直接返回
            if x == m-1 and y == n-1:
                return d
            
            # —— 0-权重边：传送门 —— 
            c = matrix[x][y]
            if 'A' <= c <= 'Z' and portal_map[c]:
                for px, py in portal_map[c]:
                    # 如果更优，就更新并放到队头
                    if dist[px][py] > d:
                        dist[px][py] = d
                        dq.appendleft((px, py))
                # 清空，保证每个字母只传送一次
                portal_map[c].clear()
            
            # —— 1-权重边：四方向普通移动 —— 
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if (0 <= nx < m and 0 <= ny < n 
                    and matrix[nx][ny] != '#'
                    and dist[nx][ny] > d + 1):
                    dist[nx][ny] = d + 1
                    dq.append((nx, ny))
        
        # 如果永远到不了，就返回 -1
        return -1

为什么这次能正确并高效？

0-1 BFS
- 我们把「传送」当成权重 0 的边，用 dq.appendleft；
- 把「走一步」当成权重 1，用 dq.append。这样就能像 Dijkstra 一样在 $O (V + E)$ 内找到最短路，而且写法非常简洁。
只存距离，不存状态集合
- dist 数组大小恰为 $m \times n$ ，不管传送门怎么组合都不膨胀。
每个字母只传送一次
- 访问过一次之后立即 portal_map[c].clear()，之后再遇到同一字母就跳过，符合「每个传送门字母最多用一次」的要求。
通用性
- 可通过所有边界情况，包括示例 1、示例 2 以及 [".A","CA"] 这类起步后直接传送的场景。

这样既保证了正确性，也把内存压到了 $O (m n)$ 。

M3552.网络传送门旅游 ​

M3552.网络传送门旅游