算法训练-黑白格子

题目描述
输入一个n*n的黑白图像（1表示黑色，0表示白色）,任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点，就说他们属于同

一个八连块。
输入有多组，第一个数输入n(n<=200)，表示n*n的数组
输出有几个八连块
样例输入：
6
1 0 0 1 0 0
0 0 1 0 1 0
0 0 0 0 0 0
1 1 0 0 0 0
1 1 1 0 0 0
0 1 0 1 0 0
样例输出：
3

本题的目的是训练图的搜索
AC代码：

#include<stdio.h>
#include<string.h>
int a[210][210];
int flag[210][210],n;
void dfs(int x,int y)
{
     if(flag[x][y]==1||a[x][y]==0)
     return;
     flag[x][y]=1;
     //递归寻找上下左右等八个区域  
     if(x-1>=0&&y-1>=0) 
     dfs(x-1,y-1);
     if(x-1>=0) 
     dfs(x-1,y);
     if(x-1>=0&&y+1<n) 
     dfs(x-1,y+1);
     if(y-1>=0) 
     dfs(x,y-1);       
     if(y+1<n)       
     dfs(x,y+1);
     if(x+1<n&&y-1>=0)       
     dfs(x+1,y-1);
     if(x+1<n) 
     dfs(x+1,y);
     if(x+1<n&&y+1<n)
     dfs(x+1,y+1);
     return;
}
int main()
{
    int i,j,sum;
    while(scanf("%d",&n)!=EOF)
    {
       sum=0;
       memset(flag,0,sizeof(flag));
       for(i=0;i<n;i++)
       for(j=0;j<n;j++)
       scanf("%d",&a[i][j]);
       for(i=0;i<n;i++)
       for(j=0;j<n;j++)
       {
          if(a[i][j]==1&&flag[i][j]==0)
          //搜索所有原来没有被搜到过的黑色格子的周围 
          //将它周围所有的黑的格子都标记为被搜索过
          //因为它们是属于一个“八格子”的 
          {dfs(i,j);sum++;}
       } 
       printf("%d\n",sum);
    }
    return 0;
}
 

代码为原创，转载请注明出处！