TZOJ 3533 黑白图像(广搜)

描述

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

输入

第1行输入一个正整数n（n≤700），此后输入n行，每行是由n个0或1组成的字符串。

输出

在输入黑白图像中，八连块的个数

样例输入

6
100100
001010
000000
110000
111000
010100

样例输出

3

题意

求图中有几个八连块

题解

这题直接广搜，深搜递归太深会爆栈

代码

 #include<stdio.h>

 #include<queue>

 using namespace std;

 char a[][];

 int dx[]={,,,,,-,-,-};

 int dy[]={,,-,,-,,,-};

 int n;

 struct point{int x,y;};

 bool check(int x,int y)

 {

     if(x>=&&x<n&&y>=&&y<n)

         return true;

     return false;

 }

 void bfs(int x,int y)

 {

     queue<point> qu;

     point h,t;

     a[x][y]='';

     h.x=x;h.y=y;

     qu.push(h);

     while(!qu.empty())

     {

         h=qu.front();

         qu.pop();

         for(int i=;i<;i++)

         {

             t.x=h.x+dx[i];

             t.y=h.y+dy[i];

             if(check(t.x,t.y)&&a[t.x][t.y]=='')

             {

                 a[t.x][t.y]='';

                 qu.push(t);

             }

         }

     }

 }

 int main()

 {

     int ans=;

     scanf("%d\n",&n);

     for(int i=;i<n;i++)

         gets(a[i]);

     for(int i=;i<n;i++)

         for(int j=;j<n;j++)

             if(a[i][j]=='')

                 ans++,bfs(i,j);

     printf("%d\n",ans);

     return ;
 }