225
算法训练-黑白格子
题目描述
输入一个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;
}
代码为原创，转载请注明出处！
最后更新：2017-04-03 12:55:41