第一次做信息学奥赛一本通1359这道“围成面积”时我的第一反应是去判断每个0是否落在由1构成的闭合曲线内部。于是射线法、奇偶校验这些几何算法全在脑子里过了一遍写出来的代码又长又难调。最尴尬的是样例跑了几个觉得没问题自己随手造一个稍微畸形一点的图就翻车。后来看到题解里的Flood fill才意识到这道题考的从来不是几何判断而是连通性遍历你根本不需要知道哪个点在内部只需要从图外面开始灌水把所有能流到的0都标记出来剩下的0自然就是被1围住的部分。这篇文章写给三类人正在刷一本通但被1359卡住的初学者准备竞赛但还分不清BFS/DFS的新手以及想搞明白Flood fill到底怎么建模的算法爱好者。我会先从题目条件入手把“围成面积”这句话翻译成人话再给出BFS、DFS两套完整可提交的C代码最后专门讲我在评测中真实遇到过的几个坑。文章里的代码我都用多组边界数据验证过可以直接拿去对照修改。1. 把这题的条件先摆清楚什么算“围成”什么算“面积”1.1 原题常见描述与输入约定信息学奥赛一本通1359这道题最常见的版本是给一个10×10的二维数组每个格子是0或11看成围墙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]; queuepairint, 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×nn可能到100甚至1000DFS的递归深度最坏情况下会到几万层。部分评测环境默认栈空间比较小容易栈溢出表现成运行时错误或者莫名其妙崩溃。BFS用队列模拟内存占用平稳不依赖系统递归栈出问题的概率低得多。我平时刷题的习惯是只要题目没特殊要求能BFS就BFS。倒不是说DFS不能写而是竞赛环境里没时间赌栈大小。如果你坚持用DFS也要提前摸清评测机的栈限制别等提交超时了才回来改。另外DFS也有非递归写法用stack容器手动模拟栈功能等价但代码量比BFS长不少性价比不高。5. 把 Flood fill 提炼成通用模板顺便解决一串经典题5.1 通用四步模板做多了会发现Flood fill类题目基本就是四步定起点根据题目语义是从边界外部灌水还是遍历所有未访问点。定数据结构BFS队列、DFS递归或者显式栈。定扩展方式四连通还是八连通决定方向数组怎么写。定统计规则vis标记完之后原图哪些格子需要计入答案。套到本题里就是起点选(0,0)数据结构用队列四连通扩展统计原图范围内未访问的0。换成LeetCode 130时起点变成四条边界上的0统计规则变成把未标记的0改成X。框架完全不用动变的只是细节。我一般会把伪代码固定成这个样子queue 初始化 起点入队 标记起点 while 队列非空: 当前点 队首出队 for 四个方向: 计算邻居坐标 如果越界跳过 如果已访问跳过 如果是墙/障碍跳过 标记邻居 邻居入队 统计或修改所有未被标记的合法格子这套模板写熟之后基本不用动脑子就能直接套用。5.2 一道题通向一串题130和200都是亲戚Flood fill的经典变体非常多我把几个最常见的列出来题目起点选择统计/修改规则一本通1359 围成面积外圈虚拟层的(0,0)统计未访问的0数量LeetCode 130 被围绕的区域四条边界上的O未访问的O改成XLeetCode 200 岛屿数量所有未访问的1访问一个连通块计数加1一本通细胞计数所有未访问的非0格子统计连通块个数图像处理魔棒选区鼠标点击的像素同色像素标记选区你看核心都是同一个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你会发现连模板都懒得换。