题目重点：两篇 onsite 记录提到八方向机器人与障碍/双机器人追问；本文只实现明确的单机器人可达集合，并标明对角穿角约定。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版矩形 grid 中 0 可走、1 障碍；输入起点 (row,column)，输出所有可达坐标集合。
- 对角移动只要求目标格可走，允许从两个正交障碍夹角穿过；题目未明确规则，若禁止穿角需额外检查侧邻格。
- 双机器人追问可能要求可达集合并集、交集、是否相遇或最短同时行动路径，题目未明确，不指定一种为原题。
解题路线
- 检查输入矩形和起点是否合法；起点在障碍上则返回空集合。
- 用 BFS 队列存已发现格，每弹一格枚举八个方向，坐标合法、可走且未访问才入队；入队时立刻标记避免重复。
- 单障碍变体把该格标为不可走后重新遍历；若有大量动态障碍更新和查询，再讨论连通性索引，不能把一次 BFS 缓存结果直接复用。
- 双机器人先问目标：若只求各自可达区域，分别跑 BFS 再求并/交；若求同步相遇，状态是两个位置与时间，规模可远大于单机器人。
手动走一遍
3×3 网格中起点 (0,0)，若 (1,0)、(0,1) 都是障碍，但 (1,1) 可走，本训练版允许对角进入 (1,1)。禁止穿角版本会在这一步停住，因此这组是澄清规则的关键测试。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Eight-neighbor reachable cells; diagonal corner cutting is allowed."""
from collections import deque
def reachable_cells(grid: list[list[int]], start: tuple[int, int]) -> set[tuple[int, int]]:
if not grid or not grid[0]:
return set()
rows, columns = len(grid), len(grid[0])
if any(len(row) != columns for row in grid):
raise ValueError("grid must be rectangular")
row, column = start
if not (0 <= row < rows and 0 <= column < columns) or grid[row][column] != 0:
return set()
seen = {start}
queue = deque([start])
while queue:
row, column = queue.popleft()
for row_delta in (-1, 0, 1):
for column_delta in (-1, 0, 1):
if row_delta == column_delta == 0:
continue
neighbor = (row + row_delta, column + column_delta)
nr, nc = neighbor
if 0 <= nr < rows and 0 <= nc < columns and grid[nr][nc] == 0 and neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
return seen
复杂度
R×C 网格每个可走格最多入队一次，时间 O(RC)、visited 与队列 O(RC)；两个独立机器人可分别跑 O(RC)，同步状态搜索可能达到 O((RC)²) 状态。
易错点与追问
容易失分的边界
- 只写四方向模板，漏对角。
- 未问穿角规则就在阻挡的两格之间斜穿。
- 双机器人目标不明却编出同步相遇规则。
- 入队后才标 visited，导致重复入队。
继续深挖
- 若两个机器人必须在相同时间到同一格，状态和碰撞约束怎么定义？
- 障碍变化后，缓存的可达集合何时失效？
- 网格极大但障碍稀疏，怎样避免扫描全部格子？
