TikTok 迷宫 BFS：单位步最短路与端点合同

题意与假设

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

• 只给BFS迷宫题名，具体格值/邻接/端点未披露。训练0可走、1阻塞、四邻接、每步1，端点显式给出。
• 代码不修改输入；无路或阻塞端点返回-1，越界和非矩形拒绝。

解题路线

1. BFS按距离层扩展，每格第一次入队时距离最短；入队即标seen，避免同层重复加入造成过量工作。
2. 起点距离0，不把访问一个格子误计为移动一步。起终点同且可走直接0。
3. 如允许斜移、传送或带权格，邻接和距离算法改变，不能拿此训练版当通用真题细则。
4. 验证用小图全对最短路独立参考，检查无解与被墙隔开的情况。

手动走一遍

[[0,0],[1,0]]从(0,0)到(1,1)需2步；(1,0)作为终点阻塞返回-1。一格0，起点终点相同结果0。

Python 参考实现

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

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

from collections import deque


def maze_distance(grid, start, end):
    """Rectangular 0/1 grid, 0 passable, four-neighbor unit moves; -1 unreachable."""
    if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
        raise ValueError('nonempty rectangular grid required')
    if any(v not in (0, 1) for row in grid for v in row):
        raise ValueError('binary grid required')
    rows, cols = len(grid), len(grid[0])
    for r,c in (start,end):
        if not (0 <= r < rows and 0 <= c < cols):
            raise ValueError('endpoint out of range')
    if grid[start[0]][start[1]] or grid[end[0]][end[1]]:
        return -1
    queue = deque([(start,0)]);seen={start}
    while queue:
        (r,c),distance=queue.popleft()
        if (r,c)==end:
            return distance
        for dr,dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr,nc=r+dr,c+dc
            if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==0 and (nr,nc) not in seen:
                seen.add((nr,nc));queue.append(((nr,nc),distance+1))
    return -1

复杂度

R×C网格 O(RC)时间和空间，输入校验也O(RC)；路径重建额外存前驱，不只返回距离。

易错点与追问

容易失分的边界

• 出队才seen导致重复。
• 误把带权问题也用普通BFS。
• 擅自从题名补传送规则。

继续深挖

• 带0/1边权为何用deque？
• 如何输出实际最短路径？