E. The Lakes - 题解
比赛与标签
比赛: Codeforces Round 871 (Div. 4) 标签: dfs and similar, dsu, graphs, implementation 难度: *1100
来探索湖泊的秘密吧喵~
主人，你好呀~！(ฅ'ω'ฅ) 这道题目给了我们一张 n x m 的地图，地图上的每个格子里都有一个数字，代表那里的水深哦。如果一个格子的水深是0，那就说明是陆地啦。
一个“湖泊”呢，就是一片连在一起的水域（水深>0）。只要能从一个水格通过上、下、左、右移动到另一个水格，它们就属于同一个湖泊的说。
湖泊的“体积”就是这个湖泊里所有格子的水深加起来的总和。我们的任务，就是要找出地图上最大的那个湖泊，把它的体积算出来，告诉裁判喵~！
喵喵的寻宝思路！
看到这种在格子上找连通块的问题，本喵的直觉就告诉我是图的遍历问题！每个有水的格子都可以看作一个节点，相邻的水格之间有一条边。我们的目标就是找到最大的连通块，并且计算这个连通块所有节点的权值（水深）之和，对吧？
所以呀，我们可以遍历整个地图的每一个格子。当我们找到一个有水（深度 > 0）而且我们还没“探索”过的格子时，就说明我们发现了一个新的湖泊！
从这个新发现的格子开始，我们就可以进行一次“探险”，把整个湖泊都找出来。这种探险可以用 深度优先搜索（DFS） 或者 广度优先搜索（BFS） 来实现。AC代码用的是BFS，那我们就来讲讲BFS是怎么做的呐~
BFS的思路就像往平静的湖面扔一块小石子，水波会一圈一圈地向外扩散，对吧？
- 准备工作: 我们准备一个小本本（也就是队列
queue）来记录接下来要去的地方。 - 发现新湖泊: 当我们从
(i, j)这个格子出发时，先把它记在小本本上，然后准备一个变量current_volume来计算当前湖泊的体积。 - 开始探索: 只要小本本上还有记录，我们就取出一个位置
(r, c)去探险。 - 累加与标记: 把
(r, c)的水深加到current_volume里。最关键的一步来啦！为了防止我们重复计算或者迷路，我们把这个格子探索完之后，就把它“填平”！也就是把它的水深设为0。这样，它就变成了陆地，我们之后就不会再从这个格子开始一次新的探索了，也保证了每个湖泊只被计算一次，喵~ 这招是不是很聪明？ - 扩散: 然后，我们看看
(r, c)的上、下、左、右四个邻居。如果邻居在地图范围内，而且也是水域（水深 > 0），就把它们也记到小本本上，等下再去探索。
当小本本（队列）空了的时候，就说明与 (i, j) 相连的所有水域都被我们走遍啦！这时候 current_volume 就是这个湖泊的总體積。我们用它来更新我们的最大体积记录 max_volume。
我们继续遍历地图，直到把所有格子都检查一遍。这样就能保证找到所有湖泊，并比较出最大的那个啦！是不是很简单呢？(＾▽＾)
魔法代码全解析喵~
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
// 加速输入输出的魔法咒语喵~ 让程序跑得更快！
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
long long max_vol = 0;
// 用一个方向数组来方便地探索上下左右四个邻居~
vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 开始地毯式搜索，一个格子都不放过！ for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // 如果当前格子有水(>0)，说明我们可能发现了一个新湖泊！ if (grid[i][j] != 0) { long long vol = 0; // 准备好我们的小本本（队列），开始BFS探索 queue<pair<int, int>> q; q.push(make_pair(i, j)); while (!q.empty()) { pair<int, int> p = q.front(); q.pop(); int r = p.first, c = p.second; // 有可能同一个格子被多次加入队列，但第一次处理后它就变0了 // 所以这里加个判断，如果是0就直接跳过 if (grid[r][c] == 0) continue; // 累加体积，然后把这里填平（标记为已访问），这是最重要的技巧哦！ vol += grid[r][c]; grid[r][c] = 0; // 探索四个方向的邻居~
for (int k = 0; k < 4; k++) {
int nr = r + dirs[k].first;
int nc = c + dirs[k].second;
// 确保邻居在地图内，并且也是水域
if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != 0) {
q.push(make_pair(nr, nc));
}
}
}
// 探索完一个湖泊后，看看是不是比之前发现的都大
if (vol > max_vol) {
max_vol = vol;
}
}
}
}
cout << max_vol << '\n';
}
return 0;
}效率评估时间！
时间复杂度: O(N * M) 的说。 因为我们最多只会访问每个格子一次。当我们用BFS探索一个湖泊时，会把所有属于这个湖泊的格子都标记为0。所以外层循环虽然看起来是两层，但每个格子
(i, j)的内部BFS逻辑只会在它属于一个未被发现的湖泊时执行一次。总的来说，每个格子最多被入队和出队一次，所以总的时间复杂度和格子总数成正比，也就是 O(N * M) 呐。空间复杂度: O(N * M) 的说。 在最坏的情况下，整个地图都是一个巨大的湖泊。这时候，我们的队列（小本本）可能需要存储所有格子的坐标，所以空间复杂度是 O(N * M) 的说。
喵喵的小课堂~
这道题虽然看似简单，但里面包含了一些非常核心和常用的思想哦！
- 核心算法: 这道题是典型的图遍历问题，可以用 BFS (广度优先搜索) 或 DFS (深度优先搜索) 解决。它们都是在图或树结构中系统地访问所有节点的经典算法喵~
- Grid Traversal (网格遍历): 在二维网格上进行搜索是算法竞赛中的常见题型。通常的技巧是使用一个方向数组
dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}来方便地访问四个邻居，这样代码会更整洁。3. 标记已访问节点: 为了避免重复访问和死循环，标记“已访问”的节点是至关重要的！这道题很巧妙地利用了 “将水深置为0” 这一操作来同时完成“标记已访问”和“防止重复计算”两个任务，一举两得，非常优雅的说！如果题目不允许修改原数组，我们通常会用一个额外的visited[N][M]布尔数组来记录。以后再遇到类似在地图上找连通区域、计算区域大小/周长等问题，都可以想想是不是能用BFS或者DFS来解决哦！加油，主人！你一定可以的！(๑•̀ㅂ•́)و✧:::::::::::::::
:::