**Lake Counting ** (难度：中等) 竞技编程-提高思维

题目描述 有一个大小为 N x M 的园子，雨后积起了水。八连通的积水被认为是连接在一起的。要求计算园子里总共有多少水洼（即八连通区域内的积水区域）。

​八连通​：指的是在一个网格中，一个格子的上下左右以及对角线方向（共八个方向）都可以连接成一个连通区域。

输入格式

• 第一行输入两个整数 N 和 M，表示园子的大小。
• 接下来输入 N 行，每行有 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..

输出示例 1：

3

解释：园子里一共有三个水洼。

时间复杂度分析 我们需要对每个格子进行访问，并进行深度优先搜索（DFS）或广度优先搜索（BFS）来找出所有的水洼。最坏情况下，我们需要遍历所有的格子，因此时间复杂度为 O(N * M)，其中 N 和 M 是园子的行数和列数，最大值为 100。

解题思路：

1. ​遍历所有格子​：对于每个格子，如果它是水洼（'W'），则说明它可能是一个新的水洼的起点。
2. ​**深度优先搜索（DFS）/广度优先搜索（BFS）**​：对于每个新的水洼起点，使用 DFS 或 BFS 来访问所有与其相连的水洼格子，并将它们标记为已访问。
3. ​计数水洼​：每次发现一个新的未访问的水洼起点时，水洼的计数加 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

时间复杂度分析：

• 时间复杂度是 O(N * M)，其中 N 和 M 分别为园子的行数和列数。我们需要遍历每个格子一次，并且在每个格子上最多进行一次 DFS 搜索，所以总体复杂度是 O(N * M)。由于 N 和 M 最大为 100，最大计算量为 10000，完全可以接受。