信息学奥赛一本通1359：用Flood fill反向灌水求解围成面积

第一次做信息学奥赛一本通1359这道“围成面积”时，我的第一反应是去判断每个0是否落在由1构成的闭合曲线内部。于是射线法、奇偶校验这些几何算法全在脑子里过了一遍，写出来的代码又长又难调。最尴尬的是，样例跑了几个觉得没问题，自己随手造一个稍微畸形一点的图就翻车。后来看到题解里的Flood fill，才意识到这道题考的从来不是几何判断，而是连通性遍历：你根本不需要知道哪个点在内部，只需要从图外面开始灌水，把所有能流到的0都标记出来，剩下的0自然就是被1围住的部分。

这篇文章写给三类人：正在刷一本通但被1359卡住的初学者，准备竞赛但还分不清BFS/DFS的新手，以及想搞明白Flood fill到底怎么建模的算法爱好者。我会先从题目条件入手，把“围成面积”这句话翻译成人话，再给出BFS、DFS两套完整可提交的C++代码，最后专门讲我在评测中真实遇到过的几个坑。文章里的代码我都用多组边界数据验证过，可以直接拿去对照修改。

1. 把这题的条件先摆清楚：什么算“围成”，什么算“面积”

1.1 原题常见描述与输入约定

信息学奥赛一本通1359这道题，最常见的版本是：给一个10×10的二维数组，每个格子是0或1，1看成围墙，0看成空地，要求输出被1围成的闭合曲线内部0的个数。

注意，“面积”这个中文词很有迷惑性。它不是说让你算1组成图形的周长，也不是算1本身的占地格子数，而是算被包在里面的空白格子数。举个例子，一个由1画成的矩形框，内部有若干0，这些0的个数就是答案。该题输入一共是10行，每行10个数字，数字之间用空格分开。有的平台会把10×10改成n×n，读法完全一样，只需要把循环范围从10改成n。

1.2 面积到底数什么：一个最直观的例子

为了把“面积”这个概念钉死，我直接给一组自制的10×10样例：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

在这个样例里，1围出了一个3×3的空白区域，答案应该是9。如果你把外层1的数量也算进去，或者统计整个矩形边框内的所有格子总数，都会得到错误结果。很多初学者把“面积”理解成图形的总面积，这是这道题最大的一个坑。在纸上手动数一遍这个过程，比直接写代码更容易建立正确直觉：真正要统计的只有那些“被1包围、除了上下左右之外无路可走”的0。

1.3 “闭合”的准确含义：四连通而不是八连通

这里说的闭合，指的是四连通意义下的闭合。0的移动只能上下左右，不能斜着走。因此，判断一个0是不是在内部，最可靠的标准是：从它出发，能不能通过上下左右相邻的0，一路走到矩阵边界外。凡是能走到外面的0，都不算被围住；凡是走不出去的0，就算被围住。这也是后面我们选择从外部反向遍历的原因。

我把四连通这点单独拿出来说，是因为网上不少文章会在方向数组里加上四个斜向，变成八连通。在“围成面积”这种题里，八连通会让原本不闭合的图形变成“闭合”的，比如两个1斜对角摆放时，八连通的墙会把缺口补上，答案直接算错。一本通这类题默认就是四连通，方向数组只用上下左右，不需要加对角。

2. 正面硬刚的常见做法，为什么都容易翻车

2.1 射线法听起来很聪明，但在方格地图上处处是坑

我最早的想法是对每个0发一条水平向右的射线，统计这条线穿过多少个1。如果穿过的1是奇数，就认为这个0在内部。这个算法在几何平面里没问题，但放到由格子组成的方格地图上，立刻遇到边界判定问题：当射线刚好擦着两个1的角过去，或者穿过一段锯齿形状的1边界时，你很难定义这次到底算“穿过”还是“没穿过”。为了处理这种情况，你得额外判断射线是否经过格点、是否与边重合，代码迅速膨胀，还容易漏掉凹进去的角落。

退一步说，即使你写的射线法能在大部分数据上侥幸通过，它的前提也依赖一个很脆弱的假设：闭合曲线本身足够规则。一旦出现凹多边形，或者曲线自带小锯齿，奇偶性判断就会出各种幺蛾子。我在本地调试时甚至见过射线刚好沿着两个1的缝穿过去，结果把外部区域判成内部的情况。这种问题靠加条件修补，永远补不干净。

2.2 找“内部种子点”再扩散，存在先有鸡还是先有蛋的问题

另一类思路是：先找一个确定在内部的0，然后从这个点向四周扩散，把所有连通的0都算进面积。问题是，怎么找种子点？你仍然要回答“这个0在不在内部”，于是又绕回射线法那一套。如果图里同时有好几个封闭区域，或者一个大环里套着小环，种子点的选择会更麻烦。一个错误的种子点会把整个外部区域误判成内部，导致答案错得离谱。

这种方案还有一个隐患：如果内部区域形状很怪，比如一个螺旋形，从单个种子点扩散时，你得保证扩散规则和“内部”定义完全一致，否则会把某些夹缝漏掉。说白了，种子点思路把“判断内部”这个核心问题推迟了，并没有真正解决它。而Flood fill的巧妙之处就在于，它把“内部判断”转换成了“外部可达性判断”，后者的实现简单得多。

2.3 贴边封闭图形是绊倒大多数人的特殊情形

还有一种情况特别阴：如果1组成的围墙刚好贴着矩阵的第一行或第一列，比如第一行本身就是一排1，那从矩阵外看，这道墙把整个上半部分的入口都封住了。你如果直接从(0,0)开始DFS或者BFS，起点是墙，根本进不去，所有本该属于外部的0都会被误判成内部。

我自己第一次遇到这种情况时，样例数据全是居中的矩形，完全没考虑贴边情况。结果提交后WA，折腾了半天才发现是边界处理的问题。这也是为什么后面要反复强调补一圈虚拟0：它能让外部区域和内部区域在逻辑上彻底分离，墙贴在哪条边上都无所谓。

3. 正确姿势：从外向内 Flood fill，把问题反过来做

3.1 灌水思想：外部就是一个大连通块

想象你端着一盆水，从矩阵外面往里泼。0是空地，1是墙。水会沿着上下左右四个方向，把所有能到达的0全部浸湿。剩下的干地，就是被1围住、水怎么都流不进去的区域。这盆水的扩散过程，就是Flood fill。

这个模型的好处是，它完全绕开了“点在多边形内”的几何判断。你不需要知道某个0是不是在内部，只需要知道它能不能连通到外部。如果连通到外部，说明它没有被围住；如果不能连通到外部，那它自然就是被围住的。这个逻辑在离散网格上极其干净，不需要处理射线穿角、贴边这类模糊情况。

3.2 补一圈虚拟0的具体做法

具体做法是把数组开大一圈：原矩阵放在a[1][1]到a[10][10]，四周的a[0][]、a[11][]、a[][0]、a[][11]全部默认是0。然后从(0,0)开始灌水。

这一圈0代表的是矩阵外面的世界，它保证了无论墙贴在哪条边上，水都能先到达墙的外侧。如果原题输入是10×10，我们就开一个12×12的数组，遍历范围是0到11。为什么不直接在原坐标范围跑？因为如果最左上角那个格子正好是1，你连外部世界的第一个落脚点都没有，外部区域会被墙完全挡死。补圈之后，起点一定不是墙，因为外面这一圈本来就不该有墙。

很多教材会把这一步叫作“加外框”或者“虚拟边界”。这个技巧在Flood fill类题目里太常用了，尤其是处理“从图像边界开始反向标记”的变体。比如LeetCode 130“被围绕的区域”，基本思路完全一样，差别只是最后要把未标记的0改成X。

3.3 灌水过程中只有两类格子：能走通的0和挡路的1

在BFS/DFS的扩展过程中，遇到1就停，遇到0就继续，遇到已经访问过的格子也停。最终vis数组里，值为1代表“这个0连通外部”，值为0代表“没被访问过”。统计阶段，我们只关心原图范围内vis[i][j]==0且a[i][j]==0的格子，把它们数一遍输出即可。

注意，原图中的1不需要统计，也不需要修改。这个细节和“图像面积”类题目不同，有些题要求把闭合曲线内的0替换成特定数字，本题只要求计数。统计时也别顺手把外圈虚拟层的0数进去，那部分不属于原矩阵范围。如果忘了加i和j的范围限制，输出会莫名其妙多出一圈数字。

4. 完整实现：BFS 和 DFS 两个版本都能过

4.1 BFS完整代码与逐行解释

我先给出BFS版本，这也是我自己最常提交的写法：

#include <bits/stdc++.h> using namespace std; const int N = 12; int a[N][N]; bool vis[N][N]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int main() { for (int i = 1; i <= 10; i++) for (int j = 1; j <= 10; j++) cin >> a[i][j]; queue<pair<int, int>> q; q.push(make_pair(0, 0)); vis[0][0] = true; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx > 11 || ny < 0 || ny > 11) continue; if (vis[nx][ny]) continue; if (a[nx][ny] == 1) continue; vis[nx][ny] = true; q.push(make_pair(nx, ny)); } } int ans = 0; for (int i = 1; i <= 10; i++) for (int j = 1; j <= 10; j++) if (a[i][j] == 0 && !vis[i][j]) ans++; cout << ans << endl; return 0; }

这段代码的核心逻辑很简单：从(0,0)开始，把外部所有能走到的0全部标记。队列里存的是待扩展的格子坐标，每次取出一个，看它的上下左右四个邻居。只要邻居在原数组范围内、没被访问过、并且不是墙，就标记并入队。循环结束后，原图范围内没被标记的0就是内部空白，累加输出。

这里有一个关键点：题目输入的10×10矩阵刻意放在a[1][1]到a[10][10]，外围那一圈a[0][*]等位置自动保留为0。全局数组默认初始化就是0，所以不需要手动给外圈赋值。

4.2 DFS完整代码，几行就写完

如果你更习惯递归写法，DFS版本也很短：

#include <bits/stdc++.h> using namespace std; const int N = 12; int a[N][N]; bool vis[N][N]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; void dfs(int x, int y) { vis[x][y] = true; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx > 11 || ny < 0 || ny > 11) continue; if (vis[nx][ny]) continue; if (a[nx][ny] == 1) continue; dfs(nx, ny); } } int main() { for (int i = 1; i <= 10; i++) for (int j = 1; j <= 10; j++) cin >> a[i][j]; dfs(0, 0); int ans = 0; for (int i = 1; i <= 10; i++) for (int j = 1; j <= 10; j++) if (a[i][j] == 0 && !vis[i][j]) ans++; cout << ans << endl; return 0; }

递归版本和BFS版本唯一的区别就是把队列换成了系统递归栈。每次进入一个可走的格子，立刻标记vis为true，然后向四个方向继续深挖。代码长度确实更短，思维更直观，但递归深度问题需要留意。

4.3 为什么我更推荐用BFS

对于一本通1359，矩阵固定是10×10，两个版本都无所谓。但如果题目被泛化成n×n，n可能到100甚至1000，DFS的递归深度最坏情况下会到几万层。部分评测环境默认栈空间比较小，容易栈溢出，表现成运行时错误或者莫名其妙崩溃。BFS用队列模拟，内存占用平稳，不依赖系统递归栈，出问题的概率低得多。

我平时刷题的习惯是：只要题目没特殊要求，能BFS就BFS。倒不是说DFS不能写，而是竞赛环境里没时间赌栈大小。如果你坚持用DFS，也要提前摸清评测机的栈限制，别等提交超时了才回来改。另外，DFS也有非递归写法，用stack容器手动模拟栈，功能等价，但代码量比BFS长不少，性价比不高。

5. 把 Flood fill 提炼成通用模板，顺便解决一串经典题

5.1 通用四步模板

做多了会发现，Flood fill类题目基本就是四步：

1. 定起点：根据题目语义，是从边界外部灌水，还是遍历所有未访问点。
2. 定数据结构：BFS队列、DFS递归，或者显式栈。
3. 定扩展方式：四连通还是八连通，决定方向数组怎么写。
4. 定统计规则：vis标记完之后，原图哪些格子需要计入答案。

套到本题里就是：起点选(0,0)，数据结构用队列，四连通扩展，统计原图范围内未访问的0。换成LeetCode 130时，起点变成四条边界上的0，统计规则变成把未标记的0改成X。框架完全不用动，变的只是细节。

我一般会把伪代码固定成这个样子：

queue 初始化 起点入队 标记起点 while 队列非空: 当前点 = 队首，出队 for 四个方向: 计算邻居坐标 如果越界：跳过 如果已访问：跳过 如果是墙/障碍：跳过 标记邻居 邻居入队 统计或修改所有未被标记的合法格子

这套模板写熟之后，基本不用动脑子就能直接套用。

5.2 一道题通向一串题：130和200都是亲戚

Flood fill的经典变体非常多，我把几个最常见的列出来：

你看，核心都是同一个Flood fill，区别只在于起点从哪来、遇到什么算障碍、最后怎么处理标记结果。所以不要只把1359当成一道题背掉，要把它当成一个模型存进脑子。后面遇到“扫雷翻空白区域”也好，“迷宫寻路”也好，都会回来用这套东西。

5.3 时间和空间复杂度，基本不用慌

每个格子最多入队或入栈一次，每个格子最多被四个方向检查一次，因此总复杂度是O(nm)，n是行数，m是列数。空间上vis数组是O(nm)，队列最坏情况下需要同时容纳大量待扩展点，最坏也是O(n*m)。

这个复杂度在竞赛题里属于最基础的水平，一般不用太担心超时。真正容易出错的不是复杂度，而是边界条件和标记时机。很多WA其实都死在“入队时机不对”这种小问题上。

6. 实测中容易出事的几个细节，以及我的验证套路

6.1 入队时标记和出队时标记的差别，直接决定MLE

我见过非常多的人在这道题上交出内存超限或者时间超限，原因都是把vis[nx][ny]=true放在了从队列取出元素之后，而不是入队时。

表面上看，出队时标记好像也没问题。但实际情况是：当某个格子第一次被邻居A发现并入队后，它还没出队，vis仍然为false，于是邻居B、邻居C、邻居D也会在各自的扩展中把它再次入队。这个格子出队一次之后，又会带着它自己的四个邻居再入队一遍，造成重复扩散。在一个大面积的空白区域里，这种重复会呈指数级膨胀，队列越来越长，最后直接MLE。

正确做法很简单，入队那一刻就立即打上访问标记。这样其他邻居再看到它时，vis已经是true，会直接跳过，每个格子只会入队一次。

6.2 方向数组写错和读入格式看错是两大隐藏坑

方向数组的常见写法是：

int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};

这个顺序对应上、下、左、右。它的问题在于，dx和dy必须一一对应，一旦写成dx={0,1,0,-1}这种，就会漏掉某个方向，导致外部灌水范围不完整，面积偏大。我的习惯是固定记住这一组，每次直接复制，绝不临时手写。

读入方面，原题如果给出空格分隔的数字，用cin直接读最省事。但有些平台会把数据写成连续字符串，比如“000111000”，这种情况下需要逐行读字符串，再每个字符减'0'存进数组。两种格式肉眼很难辨别，提交前一定要盯着样例数据看清楚有没有空格。一旦读入方式错了，整个矩阵都会错位，答案自然对不上。

6.3 我每次调这类题都会跑五组自测用例

调Flood fill题目时，我建议不要只依赖样例，自己组几组边界数据才是最快排错的方式。下面是固定测试清单：

• 全0矩阵：没有围墙，所有0都连通外部，答案应为0。
• 全1矩阵：没有任何空白区域，答案应为0。
• 单个矩形环：内部3×3空白，答案应为9。
• C形开口图形：右侧留一个缺口，0能从缺口流到外部，答案应为0。
• 双环图形：两个独立闭合矩形，答案为两片内部面积之和。
• 贴边围墙：第一行全是1，内部有空白区域，答案为内部这些被围住的0数量。

其中C形开口和贴边围墙这两组最能检验补圈逻辑是否写对。C形区域的0能从缺口流到外面，所以面积应该是0；如果程序输出的不是0，说明外部灌水范围没有扩散全。贴边围墙如果不用补圈思路，直接以(0,0)为起点，很可能把墙外空白也误判成内部，一测就露馅。

最后聊一个我自己的习惯：刷Flood fill题，我不会一上来就写队列，而是先花两分钟在草稿纸上画一个小矩阵，把起点、围墙、外部连通区域标清楚，确认“从哪开始灌水”和“哪些格子要统计”。这道题想通“从外部反向灌水”之后，代码十分钟就能写完，剩下的时间全部花在验证边界条件上。如果你也被1359卡住，不妨先把这题的建模思路背下来：补一圈虚拟0，从外部灌水，统计所有没被水淹到的0。这套思路用熟了，后面遇到LeetCode 130，你会发现连模板都懒得换。