1249：Lake Counting

skystars

【题目描述】
题意：有一块N×M的土地，雨后积起了水，有水标记为‘W’，干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？

【输入】
第一行为N,M(1≤N,M≤110)。

下面为N*M的土地示意图。

【输出】
一行，共有的水洼数。

【输入样例】

1. 10 12
   
2. W........WW.
   
3. .WWW.....WWW
   
4. ....WW...WW.
   
5. .........WW.
   
6. .........W..
   
7. ..W......W..
   
8. .W.W.....WW.
   
9. W.W.W.....W.
   
10. .W.W......W.
    
11. ..W.......W.

复制代码

【输出样例】
3
【代码】
BFS做法：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct node {
int x, y;
};
int n, m, ans;
bool a[120][120];
int xx[] = { -1,1,0,0,-1,-1,1,1 };
int yy[] = { 0,0,-1,1,-1,1,-1,1 };
queue<node> q;
void bfs(int aa,int bb) {
q.push({ aa,bb });
a[aa][bb] = false;
while (!q.empty()) {
for (int i = 0; i < 8; i++) {
int x = q.front().x + xx[i];
int y = q.front().y + yy[i];
if (a[x][y] && x >= 0 && y >= 0 && x < n && y < m) {
q.push({ x,y });
a[x][y] = false;
}
}
q.pop();
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
getchar();
for (int j = 0; j < m; j++) {
char ch = getchar();
if (ch == 'W') {
a[i][j] = true;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j]) {
bfs(i, j);
ans++;
}
}
}

printf("%d", ans);
}

DFS做法：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
using namespace std;
int n, m, ans;
bool a[120][120];
void dfs(int aa, int bb)
{
a[aa][bb] = false;
for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 1; j++)
if (aa + i >= 0 && aa + i < n && bb + j >= 0 && bb + j < m && a[aa + i][bb + j])
dfs(aa + i, bb + j);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
getchar();
for (int j = 0; j < m; j++) {
char ch = getchar();
if (ch == 'W') {
a[i][j] = true;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j]) {
dfs(i, j);
ans++;
}
}
}

printf("%d", ans);
}