題目：1097. 池塘計數
題目描述
農夫約翰有一片 N?M 的矩形土地。
最近，由于降雨的原因，部分土地被水淹沒了。
現在用一個字符矩陣來表示他的土地。
每個單元格內，如果包含雨水，則用”W”表示，如果不含雨水，則用”.”表示。
現在，約翰想知道他的土地中形成了多少片池塘。
每組相連的積水單元格集合可以看作是一片池塘。
每個單元格視為與其上、下、左、右、左上、右上、左下、右下八個鄰近單元格相連。
請你輸出共有多少片池塘，即矩陣中共有多少片相連的”W”塊。
輸入格式
第一行包含兩個整數 N 和 M。
接下來 N 行，每行包含 M 個字符，字符為”W”或”.”，用以表示矩形土地的積水狀況，字符之間沒有空格。
輸出格式
輸出一個整數，表示池塘數目。
數據范圍
1 ≤ N,M ≤ 1000
時空限制
1s / 64MB
輸入樣例
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
輸出樣例
3
代碼
#include<iostream>using namespace std;typedef pair<int, int> PII;
const int MaxN = 1000 + 10, MaxM = 1000 + 10;int N, M, hh, tt = -1, vis[MaxN][MaxM], sum;
char map[MaxN][MaxM];
PII q[MaxN * MaxM];void init(){hh = 0, tt = -1;
}void insert(int x, int y){q[++ tt] = {x, y};
}void dele(){hh ++;
}bool isempty(){return hh > tt;
}void bfs(int x, int y){init();insert(x, y);vis[x][y] = 1;while(!isempty()){auto t = q[hh];dele();for(int i = t.first - 1; i <= t.first + 1; i ++){for(int j = t.second - 1; j <= t.second + 1; j ++){if(i == t.first && j == t.second){continue;}if(i < 0 || i >= N || j < 0 || j >= M){continue;}if(map[i][j] == '.' || vis[i][j]){continue;}insert(i, j);vis[i][j] = 1;}}}
}int main(){scanf("%d%d", &N, &M);for(int i = 0; i < N; i ++){scanf("%s", map[i]);}for(int i = 0; i < N; i ++){for(int j = 0; j < M; j ++){if(map[i][j] == 'W' && !vis[i][j]){bfs(i, j);sum ++;}}}printf("%d", sum);return 0;
}
結果
