2856. 仰望星空_第1行: 两个由空格分开的整数,w 和 h。 * 第2到h+1行: 每一行包含w个"*"或者".",

单点时限: 2.0 sec

内存限制: 256 MB

我仰望星空，

它是那样辽阔而深邃；

那无穷的真理，

让我苦苦地求索、追随。

我仰望星空，

它是那样庄严而圣洁；

那凛然的正义，

让我充满热爱、感到敬畏。

我仰望星空，

它是那样自由而宁静；

那博大的胸怀，

让我的心灵栖息、依偎。

我仰望星空，

它是那样壮丽而光辉；

那永恒的炽热，

让我心中燃起希望的烈焰、响起春雷。

星空有无数星座，而今天就请你数一数天空有多少星座。

假设天空为 wh 的平面，星座由相邻的星星组成。两颗星相邻的条件为横向或纵向或对角相连。如下图为 105 的天空：

…*

…***

.……

…*.

…*.

星星为 ’*’, 空白的部分为 ’.’，上图星空共有 2 个星座。

输入格式
第 1 行：两个由空格分开的整数，1<=w<=80 和 1<=h<=1000.

第 2 到 h+1 行：每一行包含 w 个 ’*’ 或者 ’.’，代表星空的组成。

输出格式
一行：表示当前星空星座的个数。

样例
input
10 5
……**
.…***
.……
….
….
15 8
.……*
….**.……
....
…...
…….…
……
…………
.…...
output
2
7

/*
思路：bfs求连通块数
*/
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct g {
	int x,y;
};
int x[8]= {1,-1,0,0,1,-1,1,-1};
int y[8]= {0,0,1,-1,1,-1,-1,1};
int w,h;
int visit[1000][2000];
char s[1000][2000];
bool text(int a,int b) {
	if(a<0||b<0||a>=h||b>=w||visit[a][b]||s[a][b]=='.')
		return false;
	return true;
}
void bfs(int a,int b) {
	g d;
	d.x=a;
	d.y=b;
	visit[a][b]=1;
	queue<g>q;
	q.push(d);
	while(!q.empty()) {
		g f = q.front();
		q.pop();
		for(int i = 0; i < 8; i++) {
			a=f.x+x[i];
			b=f.y+y[i];
			if(text(a,b)) {
				g t;
				t.x=a;
				t.y=b;
				visit[a][b]=1;
				q.push(t);
			}
		}
	}
}
int main() {
	while(cin>>w>>h) {
		memset(visit,0,sizeof(visit));
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++)
				cin>>s[i][j];
		}
		int ans=0;
		for(int i  =0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				if(s[i][j]=='*'&&visit[i][j]==0) {
					bfs(i,j);
					ans++;
				}
			}
		}
		cout<<ans<<endl;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63