信息学奥赛一本通 1249 Lake Counting

一本通 1249 Lake Counting"/>

信息学奥赛一本通 1249 Lake Counting

【题目描述】

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

【输入】

第一行为N,M(1≤N,M≤110)。

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

【输出】

一行，共有的水洼数。

【输入样例】

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

思路

我寻思着这道题能用DFS解的，但是毕竟它放在BFS里面嘛，入乡随俗哈，我们还是用BFS解答的吧，有要DFS解答代码的话，可以点个关注，私信我哈！

【AC代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 120;
int n, m, ans, q[N * N][2], dir[8][2] = { {-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1} };
char a[N][N];
void bfs(int x, int y)
{memset(q, 0, sizeof(q));int head = 0, tail = 1;q[head][0] = x;q[head][1] = y;a[x][y] = '.';//为了防止重复，变为'.'while (head < tail){for (int i = 0; i < 8; i++){int dx = q[head][0] + dir[i][0], dy = q[head][1] + dir[i][1];if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && a[dx][dy] == 'W')//搜索{q[tail][0] = dx;q[tail++][1] = dy;a[dx][dy] = '.';}}head++;//如果没有找到八连通的水，head++，退出循环}ans++;//水洼个数加一
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];//输入数据for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (a[i][j] == 'W')//搜索到水bfs(i, j);//对他的八连通区域进行广度优先搜索}}cout << ans;return 0;
}