题目重点：由 Oracle OCI 面经中的 LC 200 题号出发，给出明确训练假设、四方向遍历、复杂度和随机对照。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入为 0/1 的矩形二维网格，1 为陆地；只有上下左右连通，斜角不连通。
- 不修改原网格；空网格或零列返回 0，非矩形输入报错。字符串 '0'/'1' 输入需先转换。
解题路线
- 从左到右扫描每一格，遇到未访问的陆地就把岛屿数加一。
- 用 BFS 访问该格所在四连通分量，邻居只有在合法边界、是陆地且未访问时才入队。
- 每格最多入队一次；visited 阻止环绕重复统计。题目若允许原地改写，也可把已访问陆地改为水以减少额外空间。
手动走一遍
网格 [[1,1,0],[0,1,0],[1,0,1]] 中前三个 1 连成一岛，底行两个 1 各独立，结果是 3。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Count four-neighbor components of land without mutating the input grid."""
from collections import deque
def count_islands(grid: list[list[int]]) -> int:
if not grid:
return 0
width = len(grid[0])
if any(len(row) != width for row in grid):
raise ValueError("grid must be rectangular")
visited = set()
count = 0
for row in range(len(grid)):
for column in range(width):
if grid[row][column] != 1 or (row, column) in visited:
continue
count += 1
visited.add((row, column))
queue = deque([(row, column)])
while queue:
current_row, current_column = queue.popleft()
for next_row, next_column in (
(current_row - 1, current_column),
(current_row + 1, current_column),
(current_row, current_column - 1),
(current_row, current_column + 1),
):
if (
0 <= next_row < len(grid)
and 0 <= next_column < width
and grid[next_row][next_column] == 1
and (next_row, next_column) not in visited
):
visited.add((next_row, next_column))
queue.append((next_row, next_column))
return count
复杂度
R×C 网格遍历 O(RC)，visited 和队列最坏 O(RC)；若允许原地修改可省 visited 集合，但队列仍可能达到 O(RC)。
易错点与追问
容易失分的边界
- 把对角线也当连通。
- 入队时不立即标记，重复入队膨胀队列。
- 题目仅给题号就声称有特定障碍或动态修改追问。
继续深挖
- 若有多次翻转一个格子的查询，静态 BFS 为什么不够？
- 要求最大岛屿面积时如何复用同一遍历？
- 网格远大于内存时如何处理分块边界上的连通关系？
