题目重点：对网格每块未访问陆地启动一次 DFS，计数连通分量；区分岛屿数量与新增陆地最大面积题。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入为矩形字符网格，'1' 陆地、'0' 水，按上下左右四邻接；空网格或零列返回 0。
- 不修改调用者的 grid，用 seen 集合；若允许原地改，可把访问过的 1 置 0 降低附加空间。
- 只返回岛屿数量，不输出面积或各岛位置。
解题路线
- 按行扫描每格，遇到未访问的陆地即答案 +1，并以它为起点做 DFS/BFS，把所有可经四邻陆地到达的格子标记已访问。
- 每个陆地最多入栈一次，访问过的点不再启动新搜索；水格跳过。
- 正确性：同一次搜索恰好覆盖一个连通分量，两个不同启动点无法属于同一分量，因此启动次数等于岛屿数。
- 迭代栈避免大岛递归爆栈；先检查矩形和字符合法性，避免缺行时索引异常。
手动走一遍
网格 110/010/001 的前三个 1 以四邻相连构成一岛，右下角单独一岛，返回 2；若按对角也连接则会变成一岛，但这不是训练合同。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Count 4-neighbor connected components of land without changing input."""
def number_of_islands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
if any(len(row) != cols or any(cell not in ("0", "1") for cell in row) for row in grid):
raise ValueError("rectangular 0/1 character grid required")
if cols == 0:
return 0
seen = set()
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1" or (r, c) in seen:
continue
count += 1
seen.add((r, c))
stack = [(r, c)]
while stack:
y, x = stack.pop()
for yy, xx in ((y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)):
if 0 <= yy < rows and 0 <= xx < cols and grid[yy][xx] == "1" and (yy, xx) not in seen:
seen.add((yy, xx))
stack.append((yy, xx))
return count
复杂度
R 行 C 列，每格最多扫描和访问常数次，时间 O(RC)；seen 和 DFS 栈最坏 O(RC) 空间。
易错点与追问
容易失分的边界
- 把对角相邻当成连接。
- 同一岛里每见到一个陆地就计一次，而未先标记整个分量。
- 递归 DFS 在大岛上超过语言递归栈。
- 与 q57 的‘翻转一格后最大面积’混成一道题，输出目标不相同。
继续深挖
- 若允许修改输入，怎样做到不另建 seen？
- 若逐次动态新增陆地并询问岛屿数，如何用并查集？
- 若改成八邻接，邻接枚举和测试应怎样变？
