• Leetcode 3552. Grid Teleportation Traversal
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3552. Grid Teleportation Traversal

1. 解題思路

這一題的話核心就是一個廣度優先遍歷，我們只需要從原點開始，一點點考察其所能到達的位置，直至其最終到達終點即可。

唯一特殊的是，考慮到傳送的存在，這里會有些特殊操作，不難發現，一個端口至多發生一次傳送，否則必然可以優化路線，因此我們只需要考察每一個端口值上是否有過傳送即可。

2. 代碼實現

給出python代碼實現如下：

class Solution:def minMoves(self, matrix: List[str]) -> int:n, m = len(matrix), len(matrix[0])teleportation = defaultdict(list)for i in range(n):for j in range(m):if matrix[i][j] in "#.":continueteleportation[matrix[i][j]].append((i, j))seen = {(0, 0)}q = [(0, 0, 0, 0)]def add_teleportation(step, i, j, status):nonlocal seen, qif matrix[i][j] not in "#." and (status & (1 << (ord(matrix[i][j]) - ord('A'))) == 0):for ti, tj in teleportation[matrix[i][j]]:if (ti, tj) not in seen:heapq.heappush(q, (step, ti, tj, status | (1 << (ord(matrix[i][j]) - ord('A')))))seen.add((ti, tj))returnadd_teleportation(0, 0, 0, 0)while q != []:step, i, j, status = heapq.heappop(q)if (i, j) == (n-1, m-1):return stepif i+1 < n and (i+1, j) not in seen and matrix[i+1][j] != "#":heapq.heappush(q, (step+1, i+1, j, status))seen.add((i+1, j))add_teleportation(step+1, i+1, j, status)if j+1 < m and (i, j+1 ) not in seen and matrix[i][j+1] != "#":heapq.heappush(q, (step+1, i, j+1, status))seen.add((i, j+1))add_teleportation(step+1, i, j+1, status)if i-1 >= 0 and (i-1, j) not in seen and matrix[i-1][j] != "#":heapq.heappush(q, (step+1, i-1, j, status))seen.add((i-1, j))add_teleportation(step+1, i-1, j, status)if j-1 >= 0 and (i, j-1 ) not in seen and matrix[i][j-1] != "#":heapq.heappush(q, (step+1, i, j-1, status))seen.add((i, j-1))add_teleportation(step+1, i, j-1, status)return -1

提交代碼評測得到：耗時6943ms，占用內存147.7MB。