DoorDash VO：計算最近 DashMart 的距離

oavoservice 原創復盤：這類「從多個源出發求最短距離」的題，面試一眼就要想到 Multi-source BFS。

題目（改寫版）

給定一個二維網格，字元含義：

• D：DashMart
• O：可通行
• X：障礙不可通行

給定若干個查詢座標 locations，對每個位置返回到最近 DashMart 的最短步數（上下左右移動）。

• 如果越界，返回 -1
• 如果無法到達任何 DashMart，返回 -1
• 如果當前位置本身是 D，返回 0

關鍵思路：多源 BFS

如果對每個查詢單獨 BFS，會很慢。

更好的方法：

• 把所有 D 同時入隊（距離 0）
• BFS 擴散，得到每個格子到最近 D 的最短距離 dist[r][c]
• 然後查詢直接 O(1) 查表

複雜度

• 預處理 BFS：O(R*C)
• 每次查詢：O(1)

Python 參考實作

from collections import deque


def build_distance_to_dashmart(grid):
    if not grid or not grid[0]:
        return []

    R, C = len(grid), len(grid[0])
    INF = 10**15
    dist = [[INF] * C for _ in range(R)]
    q = deque()

    # 多源：所有 D 入隊
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 'D':
                dist[r][c] = 0
                q.append((r, c))

    # BFS
    dirs = [(1,0), (-1,0), (0,1), (0,-1)]
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != 'X':
                if dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    q.append((nr, nc))

    return dist


def query_locations(grid, locations):
    dist = build_distance_to_dashmart(grid)
    if not dist:
        return [-1] * len(locations)

    R, C = len(grid), len(grid[0])
    ans = []
    for r, c in locations:
        if not (0 <= r < R and 0 <= c < C):
            ans.append(-1)
            continue
        if grid[r][c] == 'X':
            ans.append(-1)
            continue
        d = dist[r][c]
        ans.append(-1 if d >= 10**15 else d)
    return ans

常見坑

• 網格可能沒有任何 D：那所有可達距離都應該視為 -1。
• 位置在障礙上：一般也返回 -1。
• 輸入座標越界：直接 -1。

DoorDash 的 VO 經常把 BFS 換成業務語言（DashMart/Restaurant），但本質還是最短路。oavoservice 會訓練你把業務描述迅速映射到「多源 BFS」。

需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。