题目大意
给定一个n行m列的矩阵，矩阵中每个位置 \((i,j)\) 都有一个高度，第一行可以建造蓄水池，水可以从更高的地方输送到更低的地方。目的是建造最少的蓄水池，使得输水范围覆盖最后一行。
问题转化
- 考虑尝试在第一行的每个位置建造蓄水池，每个蓄水池都能得到在最后一行的输水区间。
- 然后问题转化成了如何用最少的区间合并成 \([1,m]\) 的完整区间。
- 如果所有区间合并起来都不能覆盖，则无解。
分析
如果每个蓄水池都有多个输水区间，则区间分散难以合并，有没有可能每个蓄水池只有一段连续的区间呢，从样例来看确实如此，于是尝试证明：
如图，其中蓝色的水流是两个非连续的区间。
如果有解，必须有其他的水流覆盖漏掉的区间，如图中的红色水流，必定与蓝色水流有交汇点。然而，交汇点的高度一定，这两条水流的后续状态必定是一样的，故矛盾。所以，在有解的情况下，每个蓄水池的输水区间必定是连续的。
解题思路
标签：贪心 + BFS
- 预处理每个蓄水厂的覆盖范围
- 对第一行的每个城市，使用 BFS 或 DFS 搜索它能到达的所有城市。
- 记录每个蓄水厂能覆盖的第 \(N\) 行城市的左边界和右边界。
- 同时标记第 \(N\) 行的每个城市是否被覆盖。
- 判断是否有解
- 检查第 \(N\) 行的每个城市是否都被标记覆盖。
- 如果有未覆盖的城市，输出 0 和未覆盖城市数量。
- 区间合并
贪心思想：每次选择覆盖当前起点且右端点最远的区间。
时间复杂度
- 总时间复杂度：\(O(N \times M^2)\)
- 每次 BFS 最坏情况访问 \(N \times M\) 个点。
- 对于 \(N, M ≤ 500\)，最坏情况 \(500^3 = 1.25 \times 10^8\)，可以接受。
参考代码
#include <bits/stdc++.h>
using namespace std;// 坐标
struct node {int x;int y;
};int h[502][502]; // 海拔高度
int vis[502][502];
int n, m;
int k[502]; // 标记第N行城市是否被覆盖
int lef[502], righ[502]; // 每个蓄水厂覆盖区间的左右端点// 四个方向：上下左右
int bx[4] = {-1, 1, 0, 0};
int by[4] = {0, 0, -1, 1};queue<node> q; int main() {// 输入数据cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> h[i][j];// 对第一行的每个城市进行BFS，计算覆盖范围for (int i = 1; i <= m; i++) {memset(vis, 0, sizeof(vis));q.push(node{1, i}); // 从(1,i)开始int l = m, r = 1; // 覆盖区间的左右边界while (!q.empty()) {int nx = q.front().x, ny = q.front().y;int nh = h[nx][ny];q.pop();// 越界或已访问则跳过if (nx < 1 || ny < 1 || nx > n || ny > m || vis[nx][ny]) continue;vis[nx][ny] = 1;// 向四个方向扩展for (int j = 0; j < 4; j++) {int tx = nx + bx[j];int ty = ny + by[j];if (h[tx][ty] < nh) // 只能流向更低海拔q.push(node{tx, ty});}// 如果到达第N行，更新覆盖区间if (nx == n) {l = min(ny, l);r = max(ny, r);k[ny] = 1; // 标记该城市被覆盖}}lef[i] = l;righ[i] = r;}// 统计未覆盖的城市数量int ans1 = 0;for (int i = 1; i <= m; i++)if (!k[i]) ans1++;// 如果有城市未被覆盖，输出0和未覆盖城市数if (ans1) {cout << 0 << endl << ans1;return 0;}// 贪心选择最少的区间覆盖[1, m]int ans2 = 0; // 最少蓄水池数量int l = 1; // 当前需要覆盖的左端点int maxr = 1; // 当前能覆盖的最远右端点while (l <= m) {// 寻找左端点<=l且右端点最大的区间for (int i = 1; i <= m; i++) {if (lef[i] <= l && righ[i] > maxr)maxr = righ[i];}l = maxr + 1; // 更新需要覆盖的左端点ans2++; // 增加蓄水池计数}cout << 1 << endl << ans2;return 0;
}