NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 26 题

#include <stdio.h> 
#include <string.h> 
#define SIZE 100 
int n, m, p, count; 
int a[SIZE][SIZE]; 
void colour(int x, int y) 
{ 
 count++; 
 a[x][y] = 1; 
 if ((x > 1) && (a[x - 1][y] == 0)) 
  colour(x - 1, y); 
 if ((y > 1) && (a[x][y - 1] == 0)) 
  colour(x, y - 1); 
 if ((x < n) && (a[x + 1][y] == 0)) 
  colour(x + 1, y); 
 if ((y < m) && (a[x][y + 1] == 0)) 
  colour(x, y + 1);  
} 
int main() 
{ 
 int i, j, x, y, ans; 
 memset(a, 0, sizeof(a)); 
 scanf("%d%d%d", &n, &m, &p); 
 for (i = 1; i <= p; i++) { 
  scanf("%d%d", &x, &y); 
  a[x][y] = 1; 
 } 
 ans = 0;
for (i = 1; i <= n; i++) 
  for (j = 1; j <= m; j++) 
   if (a[i][j] == 0) { 
    count = 0; 
    colour(i, j); 
    if (ans < count) 
     ans = count; 
   } 
 printf("%d\n", ans); 
 return 0; 
} 

输入： 6 5 9 1 4 2 3 2 4 3 2 4 1 4 3 4 5 5 4 6 4 输出：_________

拿到题先别急着跑代码，把网格画出来标上障碍。这题本质就是 Flood Fill（连通块大小），从每个'0'出发用DFS把能连通的'0'都染成1，记录每次染色的数量，最后取最大值。

最容易栽跟头的是把DFS里访问过的点当成障碍处理，或者没注意题目里障碍和已访问点都用1表示，导致重复计数；还有人会死板地数格子，忽略连通性，把不相连的0当成一块；另外输入里n是行数m是列数，别搞反了边界判断条件，不然数组越界就完蛋了。

考察知识点

这道题考的是DFS（深度优先搜索）配合 Flood Fill（泛洪填充）求连通块大小。在信息学竞赛里，这类题通常披着‘染色’‘洪水’‘区域分割’的外衣，核心就是从一个起点出发，把所有能到达的同类点都标记一遍，最后数数有多少个被标记的点。

代码与逻辑拆解

先看看colour函数这段核心代码：

void colour(int x, int y) {
  count++; a[x][y] = 1;
  if (x>1 && a[x-1][y]==0) colour(x-1,y);
  if (y>1 && a[x][y-1]==0) colour(x,y-1);
  if (x<n && a[x+1][y]==0) colour(x+1,y);
  if (y<m && a[x][y+1]==0) colour(x,y+1);
}

这里有个很关键的细节：函数一开始就把当前点染成1，然后再递归。这意味着，只要这个点被colour访问过，它就会被永久标记为1，和题目里输入的障碍点（也是1）在数组里一模一样。所以后续再遇到这个位置时，a[x][y]==0的判断就会直接跳过，不会重复走进去。这就是为什么DFS能正确统计一个连通块的大小——它把整个块‘吃’掉，剩下的0就是新的块。

再看main函数里那两层循环：

for (i = 1; i <= n; i++)
  for (j = 1; j <= m; j++)
   if (a[i][j] == 0) {
    count = 0;
    colour(i, j);
    if (ans < count) ans = count;
   }

这段就是标准的‘枚举起点’套路：遍历网格里的每个位置，如果它是0（说明还没被染过，也就是还没被任何连通块覆盖过），那就从这里开始一次DFS，把这一块的大小记进count，然后更新全局最大值ans。注意每次DFS前要把count清零，不然会累加错误。