DoorDash VO 面试题：计算最近 DashMart 的距离（二维网格多源 BFS / 最短路径）

# DoorDash VO 面试题：计算最近 DashMart 的距离（二维网格多源 BFS / 最短路径）

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，获得真题。