解题思路

这道题是在 N 行 M 列的游泳池里，找出水深相同、并且上下左右相邻的最大一片区域有多大。

这是经典的连通块问题，用深搜来做。

思路：

1. 依次看每一个格子，如果这个格子还没被访问过，就把它当作一片新区域的起点
2. 从起点开始深搜：先标记当前格子已经访问过，再看上、下、左、右四个方向
   • 如果邻居格子没有出界、没有访问过、而且水深和当前格子一样，就继续往这个邻居深搜
3. 每走到一个新格子，这片区域的面积就加 1
4. 深搜结束后，就得到这一片区域的面积，拿它和当前最大值比较，取更大

为什么要标记访问过？ 同一个格子不能数两遍，标记过了才不会把同一片区域重复计算，也不会死循环。

举例：样例中 3 行 3 列的水深是

124 224 152

• 水深 2 的三个格子 (1,2)(2,1)(2,2) 相邻，连成一片，面积是 3
• 水深 4 的两个格子 (1,3)(2,3) 相邻，面积是 2
• 剩下的水深 1、1、5 都是孤零零的格子，面积各是 1

所以最大一片区域的面积是 3。

参考代码

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

int n, m;              // 游泳池有 n 行 m 列
int a[105][105];       // a[i][j] 表示第 i 行第 j 列的水深
bool vis[105][105];    // vis[i][j] 记录这个格子有没有访问过
int dx[4] = {-1, 1, 0, 0};  // 上、下、左、右的行变化
int dy[4] = {0, 0, -1, 1};  // 上、下、左、右的列变化

// 深搜：从 (x,y) 出发，把相邻且水深相同的格子都走一遍
// 返回这一片区域一共有多少个格子
int dfs(int x, int y) {
    int cnt = 1;       // 当前格子先算一个
    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 <= n && ny >= 1 && ny <= m
            && !vis[nx][ny] && a[nx][ny] == a[x][y]) {
            cnt += dfs(nx, ny);
        }
    }
    return cnt;
}

int main() {
    cin >> n >> m;
    // 输入 n 行，每行是一个连续的数字串，如 "124"
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        // 把字符串里的每个字符转成数字存进数组
        for (int j = 1; j <= m; j++) {
            a[i][j] = s[j - 1] - '0';
        }
    }

    int maxn = 0;  // 记录最大的区域面积
    // 依次检查每一个格子
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 没访问过的格子，就是一片新区域的起点
            if (!vis[i][j]) {
                int cnt = dfs(i, j);  // 算出这片区域的大小
                if (cnt > maxn) maxn = cnt;  // 更新最大值
            }
        }
    }
    cout << maxn;  // 输出最大区域面积
    return 0;
}

复杂度分析

• 时间复杂度：O(N×M)，每个格子最多被访问一次
• 空间复杂度：O(N×M)，访问标记数组和深搜递归栈