统计八连块

试题描述

输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横竖或者对角线方向），就说它们属于同一个八连块。例如，下图中有两个八连块。

输入

第一行包括两个正整数m和n，由空格隔开，接下来的m行，每行n个字符，字符只包括“*”和“@”。

输出

一个自然数，表示八连块的个数。

输入示例

5 5
****@

*@@*@

*@**@

@@@*@

@@**@

输出示例

其他说明

数据范围：0<m,n<101。

一道非常经典的广搜题。

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 using namespace std;
 8 int map[101][101];
 9 int n,m,ans;
10 void bfs(int x,int y)
11 {
12     if(x<0 || x>=n || y<0 || y>=m) return ; 
13     if(map[x][y]<1) return ;
14     map[x][y]=-1;  //设为已访问 
15     bfs(x-1,y-1);bfs(x-1,y);bfs(x-1,y+1);  //向八方搜索 
16     bfs(x,y-1);bfs(x,y+1);
17     bfs(x+1,y-1);bfs(x+1,y);bfs(x+1,y+1);
18 }
19 
20 int main()
21 {
22     scanf("%d%d",&n,&m);
23     for(int i=0;i<n;i++)
24     {
25         for(int j=0;j<m;j++)
26         {
27             char a;
28             cin>>a;
29             if(a=='@') map[i][j]=1;
30             else map[i][j]=0;
31         }
32     }
33     for(int i=0;i<n;i++)
34         for(int j=0;j<m;j++)
35             if(map[i][j]==1) {ans++;bfs(i,j);}  //每一次退出都表明着新一轮搜索的开始。因此先加上这一个 
36     printf("%d",ans);
37     //system("pause");
38     return 0;
39 }

统计八连块