題目描述
你有一張沙漠地圖（格子）：
.：沙地（可通行）c：小車起點o：綠洲終點r：岩石（不可通行）
小車每移動一格消耗 1 單位油量。給定 gas，判斷是否能在油量耗盡前從 c 到達 o。
解題思路
這是有障礙的格子最短路問題。用 BFS 求最短步數：
- BFS 找到從
c到o的最短距離d - 若
d <= gas回傳 True，否則 False
Python 參考實作
from collections import deque
def can_reach(desert: list[list[str]], gas: int) -> bool:
R, C = len(desert), len(desert[0])
start = end = None
for r in range(R):
for c in range(C):
if desert[r][c] == 'c':
start = (r, c)
elif desert[r][c] == 'o':
end = (r, c)
if not start or not end:
return False
q = deque([(start[0], start[1], 0)])
seen = {start}
while q:
r, c, d = q.popleft()
if (r, c) == end:
return d <= gas
if d == gas:
continue
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen:
if desert[nr][nc] != 'r':
seen.add((nr, nc))
q.append((nr, nc, d + 1))
return False
複雜度
- 時間：
O(R*C) - 空間：
O(R*C)
需要面試輔助服務？聯絡 OA VO Service
- 📧 Email: [email protected]
- 📱 Phone: +86 17863968105
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。