题目重点：Nvidia 面经中的 0/1 地块种树：新树不能与旧树或新树四方向相邻。本文先给可行且极大的训练解，再区分最多棵目标。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版返回一组新树坐标，不修改输入；行优先扫描能种就种，得到极大可行集合。极大指再不能追加，不代表数量最多。
- 网格必须为非空矩形 0/1；原有树之间即使相邻也不删除，因为约束针对新栽树。
- 若实际题目要求最多能种几棵或输出所有最优布局，本训练实现不满足，需要换成最大独立集算法。
解题路线
- 复制网格状态。行优先扫描每个空格，查看上、下、左、右；若四邻都没有已有或新栽的树，就种一棵并记下坐标。
- 由于每次种树前都检查四邻，输出不会有新树与旧树或两棵新树四邻冲突；扫描结束后所有剩余空格至少挨着一棵树，所以结果是极大的。
- 若面试官要求最大数量，先筛出不挨旧树的候选格；这些格构成网格二分图。最大独立集数量可由候选点数减最大匹配得到，不能继续把简单贪心当最优解。
手动走一遍
网格 [[0,0,0],[0,0,1]] 中，行优先贪心先种 (0,0)，其余可行位置受约束，最后只种 1 棵；但选择 (0,1) 与 (1,0) 能种 2 棵。这个反例说明必须先问“任意可行布局”还是“最多棵”。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def choose_tree_positions(grid):
"""Row-major maximal placement; not guaranteed to maximize tree count."""
if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
raise ValueError("grid must be nonempty and rectangular")
if any(cell not in (0, 1) for row in grid for cell in row):
raise ValueError("grid cells must be 0 or 1")
rows, cols = len(grid), len(grid[0])
planted = [row.copy() for row in grid]
positions = []
for row in range(rows):
for col in range(cols):
if planted[row][col] != 0:
continue
if any(
0 <= row + dr < rows
and 0 <= col + dc < cols
and planted[row + dr][col + dc] == 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1))
):
continue
planted[row][col] = 1
positions.append((row, col))
return positions
复杂度
R×C 个格各检查至多四邻，训练版时间 O(RC)、复制网格空间 O(RC)、输出最多 O(RC)。最大化版本需要构造候选格图并求最大匹配，复杂度高于一次贪心扫描。
易错点与追问
容易失分的边界
- 只检查已有树，不把刚栽的新树写入状态，可能选出相邻的两棵新树。
- 把对角相邻也判为冲突，强加了题目没有的限制。
- 把极大误说成最大，忽略行优先贪心可能少种树的反例。
- 原有树彼此相邻时直接拒绝整张图；题目只约束新栽的树，是否要求旧图合法应先问。
继续深挖
- 若只问哪些单独格子可种，只需输出所有不挨已有树的空格；这些格子不能保证可以同时全种。
- 若要求最多棵，利用棋盘黑白染色将候选格构成二分图，再由最大匹配推最大独立集。
- 若有禁种地块、不同树种间距或八方向冲突，图结构和最优算法要重新分析。
