你好，同学！今天我们来攻克一个图论中的经典基础题——“岛屿数量”。在 NOI 竞赛中，这类问题被称为 “网格图连通块” 问题。它不仅考察你对搜索算法（DFS/BFS）的掌握，更是理解“隐式图”建模的绝佳案例。

一、 题目描述：岛屿数量 (Number of Islands)

题目背景： 在资源勘探中，我们需要统计地图上孤立区域的数量。

任务描述： 给你一个大小为 $M \times N$ 的二维网格 grid，表示一个地图。其中 '1' 表示陆地，'0' 表示水域。 网格中的陆地如果是在水平或垂直方向上相邻，则被视为连接在一起。你可以假设网格的四周都被水域包围。 请计算网格中“岛屿”的总数。岛屿总是被水域包围，并且通过水平或垂直连接相邻的陆地而形成。

输入格式： 第一行包含两个整数 $M$ 和 $N$，$1 \le M, N \le 300$。 接下来的 $M$ 行，每行包含 $N$ 个字符，由 '0' 和 '1' 组成。

输出格式： 输出一个整数，表示岛屿的数量。

样例 1：

输入：

4 5
11110
11010
11000
00000

输出：

1

样例 2：

输入：
4 5
11000
11000
00100
00011

输出：

3

二、 预备知识点

1. 图的遍历： 深度优先搜索 (DFS) 或 广度优先搜索 (BFS)。
2. Flood Fill (种子填充) 算法： 核心思想是从一个点出发，像水流一样充满整个连通区域。
3. 并查集 (Union-Find)： 另一种处理动态连通性问题的强大数据结构。
4. 隐式图建模： 意识到网格图中的每个格子 $(i, j)$ 是一个节点，相邻格子之间存在边。

三、 启发式引导：草稿纸上的模拟过程

请拿出草稿纸，跟我一起完成以下推演：

1. 核心思路：发现陆地，立即“沉岛”

想象你在俯瞰一片海域。你的目标是数出有多少个岛。

• Step 1: 你从网格的左上角 $(0,0)$ 开始逐行扫描。
• Step 2: 当你的眼睛看到一个 '1'（陆地）时，这就是一个新岛屿的起点！计数器 ans 加 1。
• Step 3: 为了防止之后重复计算这个岛，你必须立即把这个岛整个抹掉。
  • 怎么抹？ 从当前点出发，进行 DFS。
  • 抹掉的范围： 只要是相连的 '1'，全部变成 '0'。这就是所谓的“沉岛”操作。
• Step 4: 继续扫描，直到遍历完整个 $M \times N$ 的网格。

2. 时间与空间复杂度分析

• 时间复杂度思考： 每个格子最多被访问几次？
  • 在主循环中访问 1 次，在 DFS “沉岛”过程中最多被周围的邻居访问 4 次。
  • 结论：$O(M \times N)$。对于 $M, N \le 300$，总计算量约 $9 \times 10^4$，这在 NOI 的 1s 时限内是绰绰有余的。
• 空间复杂度思考：
  • 如果不使用显式的 visited 数组（通过修改原数组沉岛），空间开销主要是递归栈。
  • 最坏情况：全网格都是陆地，且呈蛇形连接，递归深度可达 $M \times N$。
  • 优化建议： 在 NOI 中，如果 $M \times N$ 极大（如 $10^6$），需注意栈空间溢出。此时可改用 BFS（队列实现）或手动模拟栈。

四、 算法流程图 (Mermaid)

在 C++14 实现中，我们通常使用一个全局数组或 vector。以下是基于 DFS 思路的逻辑流：

graph TD
    Start("开始扫描网格") --> LoopI("外层循环: 行 i 从 0 到 M-1")
    LoopI --> LoopJ("内层循环: 列 j 从 0 到 N-1")
    LoopJ --> Check1{"当前 grid_i_j == '1'?"}
    
    Check1 -- "是" --> Found("岛屿计数 ans 加 1")
    Found --> DFS("进入 DFS (沉岛函数)")
    
    DFS --> Mark0("将当前 grid_i_j 修改为 '0'")
    Mark0 --> Directions("递归访问上下左右相邻的 '1'")
    Directions --> DFSExit("当前连通块全部变 '0'，DFS 返回")
    
    DFSExit --> LoopJNext("继续扫描下一个列 j")
    Check1 -- "否" --> LoopJNext
    
    LoopJNext --> EndJ{"内层循环结束?"}
    EndJ -- "否" --> LoopJ
    EndJ -- "是" --> EndI{"外层循环结束?"}
    EndI -- "否" --> LoopI
    EndI -- "是" --> Output("输出 ans")

五、 读题理解关键词

在读这类“网格”或“图”题时，要注意以下关键提示：

1. “相邻”的定义： 题目明确说是“水平或垂直”（四连通）。如果包含对角线，则是“八连通”，DFS 的方向数组就需要从 4 个增加到 8 个。
2. “四周被水包围”： 这意味着你不需要处理边界外的复杂情况，只要判断索引是否越界（r < 0 || r >= M || c < 0 || c >= N）。
3. 数据范围： $300 \times 300$ 是搜索算法的黄金范围。如果范围到了 $1000+$, 就要考虑递归深度；如果到了 $10^5$ 且不是网格图，则必须用并查集。
4. 是否允许修改原数据： 题目如果没说不能改 grid，直接原地修改成 '0' 是最省空间的做法；如果不能改，则需开辟一个 bool vis[MAXN][MAXN] 数组。

教练寄语： 岛屿数量问题是“连通块”问题的母题。掌握了“扫描 + 沉岛”的节奏，你就掌握了网格图搜索的精髓！加油！