题目：奶牛和草丛

任务总览

题目描述

奶牛 Bessie 计划好好享受春天的新草。牧场由 R × C 的网格组成，奶牛想计算牧场中的​草丛数量​。

• 草丛 是由 '#' 组成的​连通区域​，可以是单个 '#' 或者相邻多个 '#'。
• ​相邻规则​：上下左右四个方向的 '#'​是相连的​，但​对角线相连的不算​。
• ​目标​：给定牧场地图，计算​草丛数量​。

输入格式

1. ​第一行​：包含两个整数 R 和 C（1 ≤ R, C ≤ 100），表示牧场的行数和列数。
2. ​接下来的 R 行​：
   • 每行包含 C 个字符，描述牧场地图。
   • 仅包含 '#'（草丛）和 '.'（空地）。

输出格式

• 输出一个整数，表示牧场中的​草丛数量​。

输入输出示例

输入示例

5 6
.#....
..#...
..#..#
....##
.....#

输出示例

3

题目分析

本题需要计算连通的 '#' 组成的草丛数量，适合使用​**深度优先搜索（DFS）或广度优先搜索（BFS）**​：

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

解法

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

• ​四个方向的偏移量​：
  • 右：(0, 1)
  • 左：(0, -1)
  • 下：(1, 0)
  • 上：(-1, 0)
• ​时间复杂度​：
  • 遍历整个 R × C 矩阵需要 ​**O(R × C)**​。
  • DFS 每个格子最多访问一次，因此总体复杂度仍为 ​**O(R × C)**​。
• ​适用场景​：
  • 适用于搜索连通区域，较少回溯。
  • 代码简洁，可直接递归。

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

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

时间复杂度分析

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