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