Bloomberg 最多穿过 k 道墙的网格最短路

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版 0 空地、1 墙，四方向每步代价 1；进入墙消耗一次额度，包括起点若是墙。
• 返回最少移动步数，不可达返回 -1；题目未给端点墙口径，训练版显式处理。

解题路线

1. 队列状态 (r,c,remaining,steps)，从起点开始 BFS；扩邻格时 remaining−grid[nr][nc]，小于 0 则跳过。
2. 同一坐标如果之前以更高或相同剩余额度、且不晚于当前距离到达，当前状态被支配；维护 bestRemaining[r][c]。
3. BFS 队列按距离非降序，首次弹出终点即最短；同距离高剩余状态可在之后继续更新其他格，仍不影响最短答案。
4. 对 k=0、1×1、墙起终点、绕路比穿墙更短和不得不穿墙的例子做手算。

手动走一遍

grid=[[0,1,0],[0,1,0],[0,0,0]]、k=1：直接从 (0,0) 向右穿墙到 (0,2) 再向下两步，共 4；绕底部也需 4。若 k=0，只能走底部路径。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import deque


def shortest_path_with_k_walls(grid, k):
    """Shortest 4-neighbor path, may enter at most k wall cells."""
    if not grid or not grid[0] or k < 0:
        return -1
    rows, cols = len(grid), len(grid[0])
    if any(len(row) != cols for row in grid):
        raise ValueError("grid must be rectangular")
    initial = k - grid[0][0]
    if initial < 0:
        return -1
    best_remaining = [[-1] * cols for _ in range(rows)]
    best_remaining[0][0] = initial
    queue = deque([(0, 0, initial, 0)])
    while queue:
        r, c, remaining, distance = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return distance
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            next_remaining = remaining - grid[nr][nc]
            if next_remaining > best_remaining[nr][nc]:
                best_remaining[nr][nc] = next_remaining
                queue.append((nr, nc, next_remaining, distance + 1))
    return -1

复杂度

每格最多以 0..k 的不同剩余量入队，保守时间 O(RCk)、队列 O(RCk)；bestRemaining 表 O(RC)。

易错点与追问

容易失分的边界

• 只用 (r,c) visited 而丢高剩余状态。
• 把穿墙理解成站在墙内免费移动。
• 没有定义起点/终点为墙。
• 用 Dijkstra 处理所有边权相同的情况而未说明为何。

继续深挖

• 若每种障碍消耗不同额度？
• 若允许对角移动？
• k≥R+C 时能否提前返回曼哈顿距离？