Meta 二值矩阵最短路：8邻接、路径长度与前驱

题目重点：在二值矩阵上求左上到右下最短路径，明确对角穿角政策并用前驱还原。

题意与假设

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

训练0可走、1障碍，允许8邻接且允许从两侧障碍之间对角穿角；矩形也支持，返回坐标path/None。若题面只允许4邻接或禁穿角，必须改转移。
路径返回list长度是经过格数，边数为len(path)−1；阻塞起终点无解，单格0返回一个坐标。

解题路线

BFS以起点入队并登记parent，出队按8方向枚举界内0格；入队即visited，第一次发现每格就是最短步数，不等出队再标记。
parent同时充当visited，仅存每格一个前驱；找到终点后反向回溯并reverse。不能为队列里每个状态复制整条路径，会造成大量重复路径空间。
无权图BFS层序距离递增，任一格第一次发现来自最早层，因此终点路径最短。若移动有不同代价，队列BFS不再保证最短，需要0-1 BFS/Dijkstra。
输入保持不变，障碍与visited分开。八方向循环排除(0,0)自步，角移动是否合法由明示合同，不从矩阵形状猜。

手动走一遍

[[0,1],[1,0]]本合同可直接对角到右下，格数2；禁穿角或4邻接则无解。[[0]]格数1，[[1]]无解。

Python 参考实现

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

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

from collections import deque


def shortest_binary_path(grid):
    """0 open/1 blocked, eight neighbors; diagonal corner cutting allowed.

    Top-left to bottom-right, return coordinate path or None; input unchanged.
    """
    if not grid or not grid[0]:return None
    rows,cols=len(grid),len(grid[0])
    if any(len(row)!=cols or any(v not in (0,1) for v in row) for row in grid):raise ValueError('rectangular binary grid required')
    start=(0,0);goal=(rows-1,cols-1)
    if grid[0][0] or grid[-1][-1]:return None
    parents={start:None};queue=deque([start])
    while queue:
        r,c=queue.popleft()
        if (r,c)==goal:
            path=[];current=goal
            while current is not None:path.append(current);current=parents[current]
            return path[::-1]
        for dr in (-1,0,1):
            for dc in (-1,0,1):
                if dr==dc==0:continue
                nr,nc=r+dr,c+dc;next=(nr,nc)
                if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==0 and next not in parents:
                    parents[next]=(r,c);queue.append(next)
    return None

复杂度

R×C格、每格最多8边，O(RC)时间/O(RC)前驱和队列，输出O(L)。一般图O(V+E)，不是O(VE)；单格存路径不能据此误称必须指数空间。

易错点与追问

容易失分的边界

visited仅按出队设置重复入队，稠密可走矩阵队列增长。
把边数和格数混淆会少1。

继续深挖

需要全部最短路时只保存单parent不足，父集合与输出可能很大。
8邻接改4邻接只变邻居集合，证明与前驱机制保留。