題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟡 ABC436D Teleport Maze

Problem Statement

題意簡述

給定一個 $H \times W$ 的迷宮，包含以下幾種格子：

. : 空地
# : 障礙物
a-z : 傳送門

你可以進行以下兩種行動：

移動：花費 1 單位時間，移動到上下左右相鄰的非障礙物格子。
傳送：若當前格子是傳送門（例如標記為 a），花費 1 單位時間，傳送到迷宮中任何標記為相同字母（a）的格子。

求從 $(1, 1)$ 移動到 $(H, W)$ 的最小行動次數。若無法到達則輸出 -1。

Constraints

條件限制

$1 \leq H, W \leq 1000$
$H \times W \geq 2$
$S_{1,1}$ 和 $S_{H,W}$ 不為 #

思路：BFS (廣度優先搜尋)

這是一個典型的網格圖最短路徑問題，邊權皆為 1，因此適合使用 BFS (Breadth-First Search) 來解決。

建模

將每個格子 $(r, c)$ 視為圖中的一個節點。

相鄰移動：對於每個格子，與其上下左右相鄰的格子之間存在一條邊（若非障礙物）。
傳送移動：對於標記為字母 $L$ 的格子，它與所有其他標記為 $L$ 的格子之間都存在一條邊。

傳送門的優化

如果直接依照上述規則建圖，對於某個字母 $L$ ，若迷宮中有 $k$ 個該字母，則兩兩之間都有邊，邊數會達到 $O(k^2)$ 。在最壞情況下（例如全圖都是 a），邊數會高達 $O((HW)^2)$ ，這會導致 BFS 超時。

關鍵優化

我們可以觀察到，當我們第一次到達某個標記為字母 $L$ 的格子並決定使用傳送功能時，我們只需花費 1 步就能到達所有標記為 $L$ 的格子。

這意味著：同一種字母的傳送機制只需要被觸發一次。

如果我們之後再次到達另一個標記為 $L$ 的格子，我們不需要再次檢查所有 $L$ 的格子，因為它們肯定已經在第一次觸發時被加入佇列（Queue）並標記為已訪問（或即將被訪問），且距離肯定不會比第一次更短。

演算法流程

預處理：使用 Hash Map (或陣列) pos 記錄每種字母出現的所有座標位置。
初始化 BFS 佇列 q，將起點 $(0, 0)$ 加入，距離設為 0。
開始 BFS：
- 取出隊首元素 (dist, r, c)。
- 一般移動：嘗試向上下左右移動，若未訪問過且非障礙，則加入 q，距離為 dist + 1。
- 傳送移動：檢查當前格子是否有字母。
  - 若是字母 ch，且該字母的傳送列表 mp[ch] 尚未被清空：
  - 遍歷 mp[ch] 中的所有座標 (nr, nc)。
  - 若 (nr, nc) 未被訪問，將其加入 q，距離為 dist + 1，並標記為已訪問。
  - 重要：處理完後，將 pos[ch] 清空，確保該字母的傳送不會被重複處理。

複雜度分析

時間複雜度： $\mathcal{O}(H \times W)$ $O (H \times W)$
- 每個格子最多進出佇列一次。
- 每個字母的傳送列表最多被遍歷一次。
- 總操作次數與網格大小成線性關係。
空間複雜度： $\mathcal{O}(H \times W)$ $O (H \times W)$
- 需要儲存網格、訪問陣列 vis 以及傳送門座標列表 pos。

Code

from collections import deque, defaultdict

def solve():
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]

    # 預處理：記錄每種字母的所有出現位置
    pos = defaultdict(list)
    for r, row in enumerate(grid):
        for c, ch in enumerate(row):
            if ch.isalpha():
                pos[ch].append((r, c))

    vis = [[False] * W for _ in range(H)]
    vis[0][0] = True
    q = deque([(0, 0, 0)])  # (dist, r, c)
    while q:
        d, r, c = q.popleft()
        if r == H - 1 and c == W - 1:
            print(d)
            return

        # 1. 上下左右移動
        for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
            if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] != '#' and not vis[nr][nc]:
                vis[nr][nc] = True
                q.append((d + 1, nr, nc))
        
        # 2. 傳送移動
        ch = grid[r][c]
        if ch.isalpha() and pos[ch]:
            for nr, nc in pos[ch]:
                if not vis[nr][nc]:
                    vis[nr][nc] = True
                    q.append((d + 1, nr, nc))
            # 關鍵：清空該字母的列表，避免重複處理
            pos[ch].clear()
    print(-1)

if __name__ == "__main__":
    solve()