解题思路

在 R 行 C 列的牧场地图里，# 表示草丛，相邻（上下左右有公共边）的 # 属于同一片草丛，问一共有多少片草丛。

这是一道数连通块的题，用深搜。

思路：

1. 从第一个格子开始，依次检查每一个格子
2. 如果发现一个格子是 # 而且还没有访问过，说明找到了一片新草丛：
   • 草丛数量加 1
   • 从这个格子开始深搜，把它上下左右、以及更远的、所有相邻的 # 全部标记成已访问
3. 这样这一片草丛就再也不会被重复数到了
4. 全部格子检查完，草丛数就是答案

为什么要标记访问过？ 深搜会把整片草丛走一遍，标记了才不会让同一片草丛被数两次。

举例：题目给的 5 行 6 列地图里，

• 第一行的那个 # 是一片草丛
• 第二、三行中间那列的两个 # 连在一起，是第二片
• 第三到五行右边那一片，是第三片 所以答案是 3。

参考代码

#include <iostream>
#include <string>
using namespace std;

int r, c;               // 牧场有 r 行 c 列
char a[105][105];       // 牧场地图，# 表示草丛，. 表示空地
bool vis[105][105];     // vis[i][j] 标记这个格子有没有访问过
int dx[4] = {-1, 1, 0, 0};  // 上、下、左、右的行变化
int dy[4] = {0, 0, -1, 1};  // 上、下、左、右的列变化

// 深搜：把 (x,y) 所在这一片草丛里的所有 # 都标记访问过
void dfs(int x, int y) {
    vis[x][y] = true;  // 标记当前格子
    // 尝试走上、下、左、右四个方向
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];  // 下一个格子的行
        int ny = y + dy[k];  // 下一个格子的列
        // 没出界、没访问过、而且也是草丛，就继续深搜
        if (nx >= 1 && nx <= r && ny >= 1 && ny <= c
            && !vis[nx][ny] && a[nx][ny] == '#') {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> r >> c;
    // 读入地图，每一行是一个只含 # 和 . 的字符串
    for (int i = 1; i <= r; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= c; j++) {
            a[i][j] = s[j - 1];
        }
    }

    int cnt = 0;  // 记录草丛的数量
    // 依次检查每一个格子
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            // 找到一个没访问过的草丛，就数一片，并把这一片全部标记
            if (!vis[i][j] && a[i][j] == '#') {
                cnt++;
                dfs(i, j);
            }
        }
    }
    cout << cnt;  // 输出草丛数量
    return 0;
}

复杂度分析

• 时间复杂度：O(R×C)，每个格子最多被访问一次
• 空间复杂度：O(R×C)，地图数组和访问标记数组