题目：数池塘（四方向）

任务总览

题目描述

农夫约翰的农场由 N × M 个方格组成，最近的降雨形成了多个​池塘​。 池塘是由相邻的‘W’（水域）格子组成的连通区域。

• 每个格子周围的 四个方向（上、下、左、右） 被认为是相连的。
• 现在给定一个​农场地图​，请计算共有​多少个池塘​。

输入格式

1. ​第一行​：两个整数 N 和 M（1 ≤ N ≤ 100, 1 ≤ M ≤ 100），表示农场的行数和列数。
2. ​接下来的 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

13

题目分析

本题要求计算​连通的水域（W）数量​，适合使用​**深度优先搜索（DFS）或广度优先搜索（BFS）**​：

1. ​遍历整个农场​，找到一个 'W'​池塘起点​。
2. ​使用 DFS/BFS 遍历整个池塘区域​，将所有相连的 'W' 标记为已访问。
3. ​每找到一个新的未访问的 'W'，池塘数量 +1​。
4. 继续遍历整个农场，直到所有池塘都被找到。

解法

方法：深度优先搜索（DFS）

• ​时间复杂度​：
  • 遍历整个 N × M 矩阵需要 ​**O(N × M)**​。
  • DFS 每个格子最多访问一次，因此总体复杂度仍为 ​**O(N × M)**​。
• ​适用场景​：
  • 适用于搜索连通区域，较少回溯。
  • 代码简洁，可直接递归。

方法：广度优先搜索（BFS）

• ​时间复杂度​：与 DFS 类似，都是 ​**O(N × M)**​。
• ​适用场景​：
  • 适用于更宽的连通区域，避免栈溢出（递归深度大时）。
  • 需要额外队列存储节点，可能消耗较多空间。

时间复杂度分析

由于 N, M ≤ 100，O(N × M) 可接受，DFS 或 BFS 都适用。