https://vjudge.net/problem/POJ-2386
由于最近的降雨，水在农夫约翰的田地上聚集，在这片田地中，每个方块都被表示为一个 N x M（1 ≤ N ≤ 100；1 ≤ M ≤ 100）的矩形。
每个方块可以是水（'W'）或干地（'.'）。农夫约翰想弄清楚他的田地上形成了多少个池塘。
池塘是由含有水的相连方块组成的集合，其中一个方块被认为与其八个邻居方块相邻。
给定农夫约翰田地的图表，请确定他有多少个池塘。
输入：
第1行：两个由空格分隔的整数：N 和 M
第2至第 N+1 行：每行 M 个字符，表示农夫约翰田地的一行。每个字符可以是 'W' 或 '.'，字符之间没有空格。 输出：
第1行：农夫约翰田地中池塘的数量。
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
数据比较小 可以锻炼下BFS 和DFS
const int N = 150;
char gra[N][N];
int n, m;
int ans;
int addx[] = { 1,-1,0,0,1,-1,1,-1 };
int addy[] = { 0,0,1,-1,1,-1,-1,1 };
void dfs(int x, int y) {
if (gra[x][y] == 'W')gra[x][y] = '.';
for (int i = 0; i < 8; i++) {
int newx = x + addx[i]; int newy = y + addy[i];
if (newx >= 0 && newx < n && newy >= 0 && newy < m && gra[newx][newy] == 'W') {
dfs(newx, newy);
}
}
}
void solve() {
ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (gra[i][j] == 'W') {
dfs(i, j);
ans++;
}
}
}
cout << ans << endl;
}
void bfs(int x,int y) {
queue<vector<int> > q;
vector<int> t; t.push_back(x); t.push_back(y);
q.push(t);
while (!q.empty()) {
int currx = q.front()[0];
int curry = q.front()[1];
q.pop();
if (gra[currx][curry] == 'W')gra[currx][curry] = '.';
else { continue; }
for (int i = 0; i < 8; i++) {
int newx = currx + addx[i]; int newy = curry + addy[i];
if (newx >= 0 && newx < n && newy >= 0 && newy < m && gra[newx][newy] == 'W') {
vector<int> t; t.push_back(newx); t.push_back(newy);
q.push(t);
}
}
}
}
void solve1() {
ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (gra[i][j] == 'W') {
bfs(i, j);
ans++;
}
}
}
cout << ans << endl;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> gra[i][j];
}
}
//solve();
solve1();
return 0;
}