魔棒点一个格子，和它四连通的同色格子全部变色——中间隔着别的颜色就渗不过去。本质就一句话：把网格当图（格子=节点、上下左右=边），从点击的格子做一次 BFS/DFS 遍历。这就是泛洪（flood fill）。
泛洪 = Photoshop 的魔棒工具：点一下一个格子，所有和它连成一片的同色格子全被选中——但「连成一片」要求上下左右挨着（四连通），斜着碰上的不算；中间隔着别的颜色（墙），水就渗不过去。把网格看成图：每个格子 = 一个节点，上下左右相邻的格子 = 一条边（8 向则连斜角也通），那么「魔棒」就是从点击的格子出发做一次图的 BFS（或 DFS），把能走到的格子全 visit 一遍。扩散时每到一个格子要问两件事：出界没？（行、列在不在 1..n、1..m 内，出界 = 掉下画布）和 去过了没？（已染色的格子水不再进）。问完都合格，才「染色 + 入队」。数岛屿、填湖、找连通块，全是这一招。
// n 行 m 列的网格：格子 (r, c) = 节点；邻居 = 上下左右（4 向） // // 4 向方向数组（上、下、左、右）： // int dr[4] = {-1, 1, 0, 0}; // int dc[4] = { 0, 0,-1, 1}; // 邻居坐标：nr = r + dr[d]，nc = c + dc[d]（d = 0..3） // // 8 向：再加 4 个斜角（上下左右斜着走） // int dr8[8] = {-1,-1,-1, 0, 0, 1, 1, 1}; // int dc8[8] = {-1, 0, 1,-1, 1,-1, 0, 1}; // // 边界判断（出界 = 掉下画布）： // bool ok(int r, int c) { return r >= 1 && r <= n && c >= 1 && c <= m; } // 每访问一个格子：4 个方向都先问 ok(nr, nc)，再问「去过/是墙没」
// 网格（1 = 墙，0 = 可淹），行 1..5、列 1..5： // 0 0 1 0 0 // 0 0 1 0 0 // 1 1 0 0 0 // 0 0 0 0 0 // 1 1 1 1 0 // // 从 (1,1) 做 BFS 泛洪（入队即标记为「已淹」）： // q = [(1,1)]，已淹 {(1,1)} // 出 (1,1)：上/左出界；下 (2,1)=0 入队；右 (1,2)=0 入队 q=[(2,1),(1,2)] // 出 (2,1)：上(1,1)已淹；下(3,1)=1墙；左出界；右(2,2)=0 入队 q=[(1,2),(2,2)] // 出 (1,2)：上出界；下(2,2)已标记；左(1,1)已淹；右(1,3)=1墙 q=[(2,2)] // 出 (2,2)：上(1,2)已淹；下(3,2)=1墙；左(2,1)已淹；右(2,3)=1墙 q=[] // 队空，结束。共淹 4 格：(1,1)、(1,2)、(2,1)、(2,2) // // 右半边那一大片（13 格）为什么淹不到？ // (2,2) 往下的 (3,2) 是墙、往右的 (2,3) 也是墙——两条路全堵死。 // （那片属于「另一座岛」，从 (1,1) 出发够不着。）
// 4 行 5 列（1 = 岛，0 = 海）： // 1 1 0 0 0 // 1 0 0 0 1 // 0 0 0 1 1 // 0 0 0 0 0 // // 套路：从第 1 行到第 4 行逐格扫描； // 遇到「还没涂过的 1」→ 一定是一座新岛：cnt++， // 从它出发泛洪，把整座岛涂成 2（涂色 = 「这座数过了」）。 // // 手推： // (1,1) 是未涂 1 → 第 1 座岛，泛洪涂 {(1,1),(1,2),(2,1)} 为 2 // (1,2) 已是 2，跳过；(1,3)(1,4)(1,5) 是 0，跳过 // (2,1) 已是 2，跳过；(2,2)(2,3)(2,4) 是 0，跳过 // (2,5) 是未涂 1 → 第 2 座岛，泛洪涂 {(2,5),(3,4),(3,5)} 为 2 // 剩下全是 0 或 2，扫描结束。cnt = 2
// 选法 1：DFS（递归）还是 BFS（队列）？ // 网格可能 1000 × 1000 = 100 万个格子。 // 递归 DFS：每进一格，调用栈上「压一层」； // 一条长路径压 100 万层，系统栈（通常只有几 MB）不够用 // → 「栈溢出」，程序直接崩。BFS 的队列开在自己管理的内存里，稳定。 // 所以泛洪默认写 BFS 版（除非题目保证网格很小）。 // // 选法 2：「数过/淹过」的标记记在哪？ // 法 A：直接改原网格（1 → 2，或 0 → 1）——省内存，原数据没了 // 法 B：原网格不动，另开 bool vis[n][m]——多占一份内存，原数据留着 // 两者效果一样，按题目要求选。 // // 小技巧：vis 用 int「编号」（时间戳），不每次都清表 // int vis[1005][1005] = {0}; int id = 0; // 每做一次泛洪：id++，访问的格子写 vis[r][c] = id； // 判断「这次来过没」= vis[r][c] == id（不是 != 0！） // → 下一次泛洪不用花 O(nm) 清整张表，id++ 一下就好。
// 4 行 5 列：1 = 岛，0 = 海；先数岛屿，再染含 (1,3) 的海区 #include <bits/stdc++.h> using namespace std; int g[5][6]; // g[1..4][1..5] int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, -1, 1}; bool ok(int r, int c) { return r >= 1 && r <= 4 && c >= 1 && c <= 5; } // 泛洪（BFS）：从 (sr,sc) 出发，把连通的 from 值整片改成 to，返回格子数 int flood(int sr, int sc, int from, int to) { queue<pair<int,int>> q; if (g[sr][sc] != from) return 0; g[sr][sc] = to; // 起点先涂 + 入队 q.push({sr, sc}); int cnt = 0; while (!q.empty()) { int r = q.front().first, c = q.front().second; q.pop(); cnt++; for (int d = 0; d < 4; d++) { int nr = r + dr[d], nc = c + dc[d]; if (ok(nr, nc) && g[nr][nc] == from) { g[nr][nc] = to; // 入队即涂色 q.push({nr, nc}); } } } return cnt; } int main() { for (int r = 1; r <= 4; r++) for (int c = 1; c <= 5; c++) cin >> g[r][c]; // ① 数岛屿：逐格扫描，见到未涂的 1 就启动一次泛洪（1 → 2） int islands = 0; for (int r = 1; r <= 4; r++) for (int c = 1; c <= 5; c++) if (g[r][c] == 1) { islands++; flood(r, c, 1, 2); } cout << islands << endl; // 样例 → 2 // ② 区域染色：(1,3) 所在的海区有多大？（0 → 1） int sr, sc; cin >> sr >> sc; cout << flood(sr, sc, 0, 1) << endl; // 样例 → 14 return 0; } // 样例输入： // 1 1 0 0 0 // 1 0 0 0 1 // 0 0 0 1 1 // 0 0 0 0 0 // 1 3 // 输出：2 // 14 ← 14 个 0 全连成一片，(1,3) 一次泛洪全染到