题目理解

这是一个 图的覆盖问题。

• 地形为 ( N \times M ) 的网格，每个格子有海拔高度。
• 蓄水厂只能建在第 1 行的城市（与湖泊相邻）。
• 输水站可以建在某个城市，当且仅当：
  • 存在一个相邻城市（四连通，即上下左右）海拔比它高
  • 并且那个相邻城市已经有了水利设施（蓄水厂或输水站）
• 目标：第 N 行（干旱区）所有城市都要有水利设施。

如果无法满足，输出第 N 行不能覆盖的城市数； 如果能满足，输出所需的最少蓄水厂数量。

思路分析

关键转化：

1. 建输水站的条件其实等价于从高处向低处流动，因此我们可以从每个蓄水厂开始，模拟水流，看它能覆盖到哪些城市。
2. 水流只能从海拔高的地方流向相邻的海拔低的地方（注意这里只能从高到低，不能平着流）。
3. 每个蓄水厂能覆盖到干旱区（第 N 行）的某些城市。这些覆盖范围是连续的区间吗？
   不是，因为地形起伏，可能覆盖第 N 行的几个不连续的城市。

子问题 1：判断能否全部覆盖

如果我们从第一行的每个城市出发，模拟水流（DFS 或 BFS），可以求出它能覆盖第 N 行的哪些城市。

如果所有第 N 行城市都能被至少一个第一行的出发城市覆盖，则能满足要求，否则不能。

子问题 2：最少蓄水厂数量

如果满足覆盖，问题变成：
已知第一行的 M 个起点，每个起点能覆盖干旱区的一些城市（即覆盖第 N 行的若干列），选择最少的起点，使得它们的覆盖范围并集是整个第 N 行。

这就是一个区间覆盖问题的变种：

• 第一行的每个城市 i 对应一个能覆盖干旱区的一个列集合（不一定是连续区间）。
• 但我们可以这样处理：对于第 N 行的每一列 j，找出所有能覆盖它的起点（第一行的列号），然后问题转化为：选择最少的起点列，使得第 N 行的每一列都被至少一个选中的起点覆盖。

这其实是一个 集合覆盖问题，在 M ≤ 500 时较难直接贪心得到最优解，需要搜索或DP。

但是，本题有一个重要性质：
对于一个起点，它覆盖的第 N 行的列集合是连续的区间。

证明思路（可以验证）：水流从高到低，地形网格上，从第一行的某个点流到第 N 行，受限于四连通且只能从高到低，因此它在干旱区覆盖的列号是连续的。
题目样例给出的图也符合这一点。

因此，问题转化为：
第一行的每个城市 i（1 ≤ i ≤ M）能覆盖干旱区的一个区间 [L[i], R[i]]（L[i] 和 R[i] 是列号，1-based）。
我们要选最少的区间，使得它们完全覆盖 1 到 M。

区间完全覆盖的贪心算法：

1. 对区间按左端点 L 排序。
2. 设当前覆盖到位置 now = 0（列从 1 开始，所以初始未覆盖）。
3. 在所有 L ≤ now+1 的区间里，选择 R 最大的，然后 now = R，答案+1，直到 now ≥ M。
4. 如果某一步找不到 L ≤ now+1 的区间，则覆盖失败（但根据前提，全覆盖是可能的）。

算法步骤

1. 从第一行的每个城市做 DFS/BFS 标记可达区域，并记录它能到达的第 N 行的最小列号和最大列号，作为区间 [L[i], R[i]]。
   • 注意：如果某个第一行城市不能到达任何干旱区城市，则它没有区间（不选它）。
2. 判断干旱区每个城市是否被至少一个区间覆盖，如果不是，则输出 0 和干旱区不能覆盖的数量。
3. 如果全覆盖，则用上述区间覆盖贪心求最少起点数。

时间复杂度

BFS/DFS 从每个第一行城市出发：O(M * N * M) 如果每次重新搜索是 O(NM²) 可能超时（N,M ≤ 500 时太大）。

优化：

• 记忆化：对于每个格子，记录能从第一行的哪些列流过来（bitset 或 bool 数组）。
  但更简单的是反向思考：
  从干旱区的每个城市出发，逆流（从低到高，相邻且高度更高）能到达第一行的哪些城市。
  这样只需要对每个干旱区城市做一次 BFS，就能知道它被哪些第一行城市覆盖。
  复杂度 O(NM) 对每个干旱区城市 BFS 最坏 O(NM) → 总 O(NM²) 还是大？
  实际上，每个干旱区城市 BFS 范围有限（因为逆流只能到更高），但最坏可能 O(NM) 每个，总共 O(NM²) 在 500²=250k 个干旱区城市？不对，干旱区只有 M 个城市，每个 BFS 最多访问所有 N×M 个格子，所以总 O(NM²) 在 500*500²=125M 可能稍大，但 BFS 有 visited 剪枝，并且每个格子只被每个起点的 BFS 访问一次，还是可能超时。

更优方法：
从第一行的每个点做一次 BFS，记录覆盖的干旱区列范围，总共 M 次 BFS，每次 O(NM) → O(NM²)，在 N=500, M=500 时是 1.25 亿操作，勉强可过（常数小的话）。
但我们可以用 DP 思想：
设 reachable[i][j] 表示能否从第一行的某个城市流到 (i,j)。
我们可以从所有第一行城市同时开始 BFS（多源 BFS），一次得到所有可达点，但这样无法区分每个起点覆盖的干旱区列区间。

因此，为了得到每个起点的覆盖区间，只能单独 BFS。
M ≤ 500，N ≤ 500，MNM=125M，在合理优化下（队列、标记数组复用）可以过。

详细步骤

1. 输入 N, M 和高度矩阵 H。
2. 对于第一行的每个列 j=1..M：
   • BFS/DFS 从 (1,j) 出发，标记所有能到达的点。
   • 记录能到达的干旱区（第 N 行）的最小列号 L[j] 和最大列号 R[j]。 如果没到达任何干旱区城市，则 L[j] = INF, R[j] = -1。
3. 检查干旱区每个城市（第 N 行，列 k=1..M）：
   • 是否被某个 j 覆盖（即存在 j 使得 L[j] ≤ k ≤ R[j]）。
   • 统计不能被覆盖的个数 cnt。
4. 如果 cnt > 0：
   • 输出 0 和 cnt。
5. 否则：
   • 收集所有 L[j] ≤ R[j] 的区间 [L[j], R[j]]。
   • 用贪心区间覆盖算法求最少区间数（即最少蓄水厂数）。
   • 输出 1 和最少数量。

贪心区间覆盖实现

区间按 L 排序，设当前覆盖到 now=0，每次从 L ≤ now+1 的区间里选 R 最大的，更新 now = R，计数+1，直到 now ≥ M。

代码框架（C++）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 505;
const int INF = 1e9;

int N, M;
int H[MAXN][MAXN];
bool vis[MAXN][MAXN];
int L[MAXN], R[MAXN]; // 第一行第j列能覆盖干旱区的区间
bool covered[MAXN];   // 干旱区第k列是否被覆盖

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs(int sx, int sy, int idx) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy] = true;
    
    L[idx] = INF;
    R[idx] = -1;
    
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        
        if (x == N) { // 干旱区
            L[idx] = min(L[idx], y);
            R[idx] = max(R[idx], y);
        }
        
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && !vis[nx][ny] && H[nx][ny] < H[x][y]) {
                vis[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

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 j = 1; j <= M; j++) {
        memset(vis, 0, sizeof(vis));
        bfs(1, j, j);
    }
    
    // 检查干旱区覆盖情况
    int cnt_uncovered = 0;
    for (int k = 1; k <= M; k++) {
        covered[k] = false;
        for (int j = 1; j <= M; j++) {
            if (L[j] <= k && k <= R[j]) {
                covered[k] = true;
                break;
            }
        }
        if (!covered[k]) cnt_uncovered++;
    }
    
    if (cnt_uncovered > 0) {
        cout << 0 << endl << cnt_uncovered << endl;
        return 0;
    }
    
    // 区间覆盖贪心
    vector<pair<int, int>> intervals;
    for (int j = 1; j <= M; j++) {
        if (L[j] <= R[j]) {
            intervals.push_back({L[j], R[j]});
        }
    }
    
    sort(intervals.begin(), intervals.end());
    
    int now = 0, ans = 0, i = 0;
    int m = intervals.size();
    
    while (now < M) {
        int max_r = now;
        while (i < m && intervals[i].first <= now + 1) {
            max_r = max(max_r, intervals[i].second);
            i++;
        }
        if (max_r == now) break; // 无法扩展
        now = max_r;
        ans++;
    }
    
    cout << 1 << endl << ans << endl;
    
    return 0;
}