日期：2026年7月1日
LeetCode 題目連結：2812. Find the Safest Path in a Grid
解題想法
中等難度題。題目給定代表地圖的二維陣列 $grid$，假設尺寸為 $n \times n$，地圖中 1 代表小偷，0 代表空地，要從位置 $(0, 0)$ 走到 $(n-1, n-1)$，找出最佳路徑上與所有小偷的最小曼哈頓距離。解題過程主要分為 2 個步驟：
- 掃過地圖每一格，從小偷的位置開始 BFS，找出所有格子與所有小偷的最短距離。
- 用最大優先佇列 $pq$，先放入 $(dist[0][0], 0, 0)$，不斷地從 $pq$ 取出資料，如果遇到位置 $(n-1, n-1)$ 回傳這格的距離；如果還沒有走到終點，對這個位置 $(r, c)$ 四方位檢查，將新的位置及距離加入 $pq$ 之中。
Python 程式碼
Runtime: 9455 ms, beats 5.21%. Memory: 41.56 MB, beats 51.73%.
class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
n = len(grid) # 地圖尺寸 n*n
# --- 特例，起點或終點有小偷，回傳 0 ---
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return 0
# --- 用 BFS 從小偷的位置開始往外，找小偷到格子的距離 ---
dist = [[1000]*n for _ in range(n)] # 測資最大為 100，預設距離為超出範圍的 1000
for i in range(n): # 掃過每一格
for j in range(n):
if grid[i][j] == 1: # 小偷
que = deque([(i, j)]) # 待走訪佇列
dist[i][j] = 0 # 這個的距離為 0
while que:
r, c = que.popleft() # 目前的位置
d = dist[r][c] # 目前的距離
# 四方位檢查，如果 (nr, nc) 沒有出界而且距離大於 d+1，更新 dist[nr][nc]，將 (nr, nc) 加入 que
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] > d + 1:
dist[nr][nc] = d + 1
que.append((nr, nc))
# --- 用最大優先佇列找出從 (0, 0) 到 (n-1, n-1) 最佳路徑上距離最小值 ---
pq = [(-dist[0][0], 0, 0)] # (-distance, row, col)
visited = set() # 已走訪的格子
while pq:
d, r, c = heapq.heappop(pq)
d = -d
visited.add((r, c))
# 走到終點，回傳 d
if r == n-1 and c == n-1:
return d
# 四方位檢查
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
visited.add((nr, nc))
newDist = min(d, dist[nr][nc])
heapq.heappush(pq, (-newDist, nr, nc))
# 預設的回傳值，用不到
return 0
