TZOJ 3533 黑白图像(广搜)

描述

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

输入

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

输出

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

样例输入

6
100100
001010
000000
110000
111000
010100

样例输出

题意

求图中有几个八连块

题解

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

代码

 1 #include<stdio.h>
 2 #include<queue>
 3 using namespace std;
 4 
 5 char a[705][705];
 6 int dx[]={1,1,1,0,0,-1,-1,-1};
 7 int dy[]={1,0,-1,1,-1,1,0,-1};
 8 int n;
 9 struct point{int x,y;};
10 bool check(int x,int y)
11 {
12     if(x>=0&&x<n&&y>=0&&y<n)
13         return true;
14     return false;
15 }
16 void bfs(int x,int y)
17 {
18     queue<point> qu;
19     point h,t;
20     
21     a[x][y]='0';
22     h.x=x;h.y=y;
23     qu.push(h);
24     
25     while(!qu.empty())
26     {
27         h=qu.front();
28         qu.pop();
29         for(int i=0;i<8;i++)
30         {
31             t.x=h.x+dx[i];
32             t.y=h.y+dy[i];
33             if(check(t.x,t.y)&&a[t.x][t.y]=='1')
34             {
35                 a[t.x][t.y]='0';
36                 qu.push(t);
37             }
38         }
39     }
40 }
41 int main()
42 {
43     int ans=0;
44     scanf("%d
",&n);
45     for(int i=0;i<n;i++)
46         gets(a[i]);
47     for(int i=0;i<n;i++)
48         for(int j=0;j<n;j++)
49             if(a[i][j]=='1')
50                 ans++,bfs(i,j);
51     printf("%d
",ans);
52     return 0;
53 }