题目重点：针对每行长度不同的网格做四邻接 BFS，求每座房屋的左上/右下边界，明确坐标字母数字映射的训练假设。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 `grid` 是每行可不同长度的 `'*'/'1'` 字符串，四邻接连通 `1`；房子可为任意形状，输出其最小轴对齐外接框，不要求框内全是房子。
- 行按 A、B…、Z、AA，列从 1 起；这只是对 `A2/B3` 的可解释映射，题目没有正式定义。按输入行优先发现顺序输出。
解题路线
- 逐行逐列扫描；未访问 `1` 作一个新房子的 BFS 源，seen 防重复，每出队一格更新 min/max row/col。
- 访问垂直邻居时必须用目标行 `len(grid[nr])` 做边界判断，不能假定矩阵是矩形或沿用当前行宽。横向邻居按同样规则检验。
- BFS 结束将 `(min_row,min_col)` 与 `(max_row,max_col)` 转成字母行+一基列号；若题意要精确房屋形状而非框，则需返回格子集合，不可只给框。
- 用不同结构的 union-find 连通分量参考模型核对 12,000 个随机短 ragged grid，包括空行、悬空列与非矩形 L 形。
手动走一遍
`['*11','*1','11*']` 中位置 (0,1),(0,2),(1,1),(2,0),(2,1) 四邻接连成一屋；边界是第 1–3 行、第 1–3 列，训练坐标为 A1 到 C3。框内 `*` 可存在。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def row_label(index: int) -> str:
label = ""
index += 1
while index:
index, remainder = divmod(index - 1, 26)
label = chr(65 + remainder) + label
return label
def house_boxes(grid: list[str]) -> list[tuple[str, str]]:
"""Training contract: '1' cells, 4-neighbor, ragged rows, A1 coordinates."""
seen = set()
result = []
for row, line in enumerate(grid):
for col, value in enumerate(line):
if value != "1" or (row, col) in seen:
continue
seen.add((row, col))
queue = deque([(row, col)])
top = bottom = row
left = right = col
while queue:
r, c = queue.popleft()
top, bottom = min(top, r), max(bottom, r)
left, right = min(left, c), max(right, c)
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < len(grid) and 0 <= nc < len(grid[nr]) and grid[nr][nc] == "1" and (nr, nc) not in seen:
seen.add((nr, nc))
queue.append((nr, nc))
result.append((f"{row_label(top)}{left + 1}", f"{row_label(bottom)}{right + 1}"))
return result
复杂度
设所有行总格数为 N，每格最多入队一次、检查常数个邻居，时间 O(N)、seen/队列/结果最坏 O(N)；不按 `rows×max_cols` 误算必有格子。
易错点与追问
容易失分的边界
- 以第一行长度约束所有行，漏掉后面更宽行或访问越界。
- 默认八邻接，把只碰角的两屋合并。
- 把外接框当满矩形房屋。
- 只更新右下角而忘记组件可能向左延伸。
- 超过 Z 行时坐标编码未定义。
继续深挖
- 如果房屋可斜向接壤，邻居规则怎么改？
- 若要求每间房的面积与周长，遍历时怎样计算？
- 超大稀疏网格如何避免存所有空格？
- 坐标原题若定义字母为列而非行，输出如何改？
