Uber 机器人网格：四向最近障碍距离匹配

题意与假设

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

• 网格为非空矩形，O 是机器人，E 是空地，X 是障碍物；只有 O 单元格可作为答案。
• 边界外第一格视为虚拟障碍。距离按从机器人格到障碍格的步数计；例如最左列且左边没有 X 时，left=1。若真实题目把边界自身计为 0，应统一改动距离约定。
• 障碍物阻挡四个轴向；不考虑斜向或机器人之间互相阻挡；返回全部匹配坐标，使用零基 (row,column)。

解题路线

1. 逐行从左到右记录上一个 X 的列号，没有则用 -1；对非 X 格令 left=c-wall。反向扫描时以列数为右侧虚拟墙，得 right。
2. 逐列从上到下记录上一个 X 的行号，没有则用 -1；再反向以行数为虚拟墙，得到 top 和 bottom。
3. 遍历 O 格，按 [left,top,bottom,right] 与目标向量逐项比较。四次扫描都维护该方向最近的真实墙或虚拟边界，故每个值就是最近障碍距离。

手动走一遍

VO 题目的五行网格中，第二行第二列的 O（零基 (1,1)）左侧和上方虚拟边界各距 2，下方边界距 4，右邻 X 距 1，向量恰是题目查询 [2,2,4,1]。

Python 参考实现

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

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

"""Find robot cells by four nearest-wall distances."""


def matching_robots(grid: list[str], target: tuple[int, int, int, int]) -> list[tuple[int, int]]:
    if not grid:
        return []
    rows, cols = len(grid), len(grid[0])
    if cols == 0 or any(len(row) != cols for row in grid):
        raise ValueError("grid must be nonempty and rectangular")
    if any(cell not in "OEX" for row in grid for cell in row):
        raise ValueError("expected O robot, E empty, X obstacle")
    left = [[0] * cols for _ in range(rows)]
    top = [[0] * cols for _ in range(rows)]
    bottom = [[0] * cols for _ in range(rows)]
    right = [[0] * cols for _ in range(rows)]

    for r in range(rows):
        wall = -1
        for c in range(cols):
            if grid[r][c] == "X":
                wall = c
            else:
                left[r][c] = c - wall
        wall = cols
        for c in range(cols - 1, -1, -1):
            if grid[r][c] == "X":
                wall = c
            else:
                right[r][c] = wall - c
    for c in range(cols):
        wall = -1
        for r in range(rows):
            if grid[r][c] == "X":
                wall = r
            else:
                top[r][c] = r - wall
        wall = rows
        for r in range(rows - 1, -1, -1):
            if grid[r][c] == "X":
                wall = r
            else:
                bottom[r][c] = wall - r

    return [
        (r, c)
        for r in range(rows)
        for c in range(cols)
        if grid[r][c] == "O"
        and (left[r][c], top[r][c], bottom[r][c], right[r][c]) == target
    ]

复杂度

设网格 R×C；四次方向扫描和一次筛选均为 O(RC) 时间，四个距离矩阵用 O(RC) 空间。若只需逐行输出且能预处理列方向，可压缩部分临时存储。

易错点与追问

容易失分的边界

• 向量顺序是 left、top、bottom、right，不能误按顺时针或常见的上下左右顺序比较。
• 最近 X 的距离与到网格边界的距离取较小值；把边界忽略会使无 X 的行列得不到答案。
• 只检查相邻 X 会漏掉远处障碍；逐机器人向四方射线扫描虽正确，最坏会重复扫描到 O(RC(R+C))。

继续深挖

• 若机器人坐标频繁变而 X 固定，可预处理四个距离表，查询任一坐标为 O(1)。
• 若障碍动态增删，可考虑按行和列维护有序障碍坐标，查询前驱/后继为 O(log(R+C))，但一次更新后若需列出所有匹配机器人仍可能扫描全部机器人。