ECNUOJ 2856 仰望星空

仰望星空

Time Limit:1000MS Memory Limit:65536KB
Total Submit:373 Accepted:145

Description 

我仰望星空，

它是那样辽阔而深邃；

那无穷的真理，

让我苦苦地求索、追随。

我仰望星空，

它是那样庄严而圣洁；

那凛然的正义，

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

我仰望星空，

它是那样自由而宁静；

那博大的胸怀，

让我的心灵栖息、依偎。

我仰望星空，

它是那样壮丽而光辉；

那永恒的炽热，

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

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

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

..*.....**

.**..*****

.*...*....

..****.***

..****.***

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

Input 

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

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

Output 

一行：表示当前星空星座的个数。

Sample Input 

10 5
..*.....**
.**..*****
.*...*....
..****.***
..****.***

15 8
**.**......*..*
..*.**.*...*...
*.*.**.*****.**
...***.****.**.
...**..*.*.....
*****..*****..*
....**...*..*..
*.*...*.*.*.***

Sample Output 

2
7

Source

解题：搜索

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int w,h;
char table[1010][90];
const int dir[8][2] = {
    -1,0,1,0,0,-1,0,1,
    -1,-1,1,1,-1,1,1,-1
};
bool isIn(int x,int y) {
    return x >= 0 && x < h && y >= 0 && y < w;
}
queue< pii >q;
void bfs(int x,int y) {
    while(!q.empty()) q.pop();
    q.push(pii(x,y));
    table[x][y] = '.';
    while(!q.empty()) {
        pii now = q.front();
        q.pop();
        for(int i = 0; i < 8; ++i) {
            x = now.first + dir[i][0];
            y = now.second + dir[i][1];
            if(isIn(x,y) && table[x][y] == '*') {
                q.push(pii(x,y));
                table[x][y] = '.';
            }
        }
    }
}
int main() {
    while(~scanf("%d%d",&w,&h)) {
        for(int i = 0; i < h; ++i)
            scanf("%s",table[i]);
        int ret = 0;
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                if(table[i][j] == '*') {
                    ret++;
                    bfs(i,j);
                }
            }
        }
        printf("%d
",ret);
    }
    return 0;
}