#include <cstdio>
#include <queue>
#include <algorithm>
#define WATER 'W'
#define LAND '.'
#define MAX_N 110
#define MAX_M 110
using namespace std;
typedef pair<int,int> P;
queue<P> que;
int map[MAX_N][MAX_M],N,M,ch;
bool inmap(int x,int y){return x > 0 && y > 0 && x <= N && y <= M;}
void bfs(P point){
    que.push(point);
    while(!que.empty()){
        P p = que.front();que.pop();
        for(int dx = -1;dx <= 1;++dx){
            for(int dy = -1;dy <= 1;++dy){
                int x = p.first + dx,y = p.second + dy;
                if(inmap(x,y) && map[x][y]){
                    map[x][y] = 0;
                    que.push(make_pair(x,y));
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    getchar();
    for(int i = 1;i <= N;++i){
        for(int j = 1;j <= M;++j){
            ch = getchar();
            if(ch == WATER){map[i][j] = 1;}
            else{map[i][j] = 0;}
        }
        getchar();
    }
    int ans = 0;
    for(int i = 1;i <= N;++i){
        for(int j = 1;j <= M;++j){
            if(map[i][j]){
                bfs(make_pair(i,j));
                ++ans;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

• Re:一A。。。BFS (1349) kimixuchen 2015-11-02 21:30:27
  • Re:一A。。。BFS (24) kimixuchen 2015-11-02 21:31:14