日期：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
Runtime: 9464 ms, beats 5.21%. Memory: 43.04 MB, beats 50.29%.
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 = [(i, j)] # 待走訪佇列
head = 0
dist[i][j] = 0 # 這個的距離為 0
while head < len(que):
r, c = que[head] # 目前的位置
head += 1
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 = [[False] * n for _ in range(n)] # 已走訪的格子
visited[0][0] = True
while pq:
d, r, c = heapq.heappop(pq)
d = -d
visited[r][c] = True
# 走到終點，回傳 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 not visited[nr][nc]:
visited[nr][nc] = True
newDist = min(d, dist[nr][nc])
heapq.heappush(pq, (-newDist, nr, nc))
# 預設的回傳值，用不到
return 0
C++ 程式碼
Runtime: 897 ms, beats 11.09%. Memory: 331.31 MB, beats 8.76%.
class Solution {
public:
int maximumSafenessFactor(vector<vector<int>>& grid) {
int n = (int)grid.size(); // 地圖尺寸 n*n
/* 特例，起點或終點有小偷，回傳 0 */
if (grid[0][0] == 1 || grid[n-1][n-1] == 1) {
return 0;
}
/* 用 BFS 從小偷的位置開始往外，找小偷到格子的距離 */
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
vector<vector<int>> dist (n, vector<int> (n, 1000));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
dist[i][j] = 0;
queue<pair<int, int>> que;
que.push({i, j});
while(!que.empty()) {
int r = que.front().first, c = que.front().second, d = dist[r][c];
que.pop();
for(int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] > d + 1) {
dist[nr][nc] = d + 1;
que.push({nr, nc});
}
}
}
}
}
}
/* 用最大優先佇列找出從 (0, 0) 到 (n-1, n-1) 最佳路徑上距離最小值 */
priority_queue<tuple<int, int, int>> pq;
pq.push({dist[0][0], 0, 0});
vector<vector<bool>> visited (n, vector<bool> (n, false));
visited[0][0] = true;
while(!pq.empty()) {
auto [d, r, c] = pq.top();
pq.pop();
if (r == n-1 && c == n-1) {
return d;
}
for(int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
visited[nr][nc] = true;
int newDist = min(d, dist[nr][nc]);
pq.push({newDist, nr, nc});
}
}
}
return 0;
}
};
沒有留言:
張貼留言