← 返回博客列表
VO Bloomberg

Bloomberg 面试题：带岩石障碍的沙漠寻路问题

2025-12-06

题目描述

在一个沙漠地图中，小车从起点 c 出发，需要到达绿洲 o。地图由以下元素组成：

小车每移动一格消耗 1 单位油。给定最大油量 gas，判断能否在油耗尽前从起点到达终点。

示例

desert = [
    ['.', '.', '.', '.', '.', '.', '.', 'o'],
    ['.', 'r', 'r', 'r', 'r', 'r', 'r', 'r'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', 'c', '.', '.', '.', '.', '.'],
]

ride(desert, 5)  -> False  # 5 格油不够绕过障碍
ride(desert, 15) -> True   # 15 格油足够到达

解题思路

这是带约束的 BFS 最短路径 问题：

  1. 找到起点 c 和终点 o 的位置
  2. 使用 BFS 从起点搜索，跳过岩石 r
  3. 如果能在 gas 步内到达终点，返回 True

Python 实现

from collections import deque

def ride(desert: list, gas: int) -> bool:
    if not desert or not desert[0]:
        return False
    
    rows, cols = len(desert), len(desert[0])
    start = end = None
    
    # 找到起点和终点
    for i in range(rows):
        for j in range(cols):
            if desert[i][j] == 'c':
                start = (i, j)
            elif desert[i][j] == 'o':
                end = (i, j)
    
    if not start or not end:
        return False
    
    # BFS
    queue = deque([(start[0], start[1], 0)])  # (row, col, steps)
    visited = {start}
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while queue:
        r, c, steps = queue.popleft()
        
        # 找到终点
        if (r, c) == end:
            return steps <= gas
        
        # 油量用尽
        if steps >= gas:
            continue
        
        # 探索四个方向
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            # 边界检查
            if 0 <= nr < rows and 0 <= nc < cols:
                # 不是岩石且未访问
                if desert[nr][nc] != 'r' and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, steps + 1))
    
    return False

返回最短距离的版本

def min_distance(desert: list) -> int:
    """返回到达终点的最短距离，无法到达返回 -1"""
    if not desert or not desert[0]:
        return -1
    
    rows, cols = len(desert), len(desert[0])
    start = end = None
    
    for i in range(rows):
        for j in range(cols):
            if desert[i][j] == 'c':
                start = (i, j)
            elif desert[i][j] == 'o':
                end = (i, j)
    
    if not start or not end:
        return -1
    
    queue = deque([(start[0], start[1], 0)])
    visited = {start}
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while queue:
        r, c, dist = queue.popleft()
        
        if (r, c) == end:
            return dist
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if desert[nr][nc] != 'r' and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, dist + 1))
    
    return -1

进阶：加油站版本

如果地图上有加油站 g，经过时可以加满油：

def ride_with_gas_stations(desert: list, tank_capacity: int) -> bool:
    """带加油站的版本"""
    rows, cols = len(desert), len(desert[0])
    start = end = None
    
    for i in range(rows):
        for j in range(cols):
            if desert[i][j] == 'c':
                start = (i, j)
            elif desert[i][j] == 'o':
                end = (i, j)
    
    # 状态：(row, col, remaining_gas)
    queue = deque([(start[0], start[1], tank_capacity)])
    visited = {(start[0], start[1], tank_capacity)}
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while queue:
        r, c, gas = queue.popleft()
        
        if (r, c) == end:
            return True
        
        if gas == 0:
            continue
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and desert[nr][nc] != 'r':
                # 加油站：加满油
                new_gas = tank_capacity if desert[nr][nc] == 'g' else gas - 1
                
                state = (nr, nc, new_gas)
                if state not in visited:
                    visited.add(state)
                    queue.append((nr, nc, new_gas))
    
    return False

复杂度分析

需要面试辅助服务？联系我们

需要面试真题？ 立刻联系微信 Coding0201，获得真题。