CJDF04｜岛屿数量 题解

核心算法

枚举所有格子；每发现一个未访问陆地，答案加一，并用 DFS 标记它所在的整座岛。

思路推导

一次 DFS 恰好覆盖一个四连通块。外层枚举再次遇到未访问陆地时，它必属于另一座岛。

正确性说明

每座岛第一次被枚举到时计数一次，随后整座岛被标记，不会重复计数；不同岛之间不连通，也不会被同一次 DFS 合并。因此答案恰为岛屿数。

复杂度

时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。

易错点

• 只对未访问的陆地启动 DFS；
• 斜向不连通；
• 全水域答案为 0。