思路与算法

按高度递增汇总每格可达底部的左右端点；另从全部顶行做真实下降遍历统计缺失底城。全可达时每个顶源覆盖的底部是区间，排序贪心最少区间覆盖。

正确性说明

严格下降边构成DAG，低处先处理使端点聚合正确。若有不可达底城，真实遍历直接给缺失数量，不利用区间近似。若全部底城可达，某源到两底城的路径与中间底城的任意另一顶源路径在平面网格必交，交点之后路径可接续，故同源也能到达中间城，可达集合连续。最左未覆盖位置选所有可覆盖区间中最远右端，交换任意最优方案首区间不增加数量，从而覆盖贪心正确。

复杂度

O(NM log(NM)+M log M)时间、O(NM+M)空间，含排序、端点和可达性数组初始化。

易错点

只有所有底城可达后才能依区间做最小覆盖；相等高度不能输水。N=1时顶行就是底行，也应按同一规则处理。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int N = n * m;
    vector<int> a(N), order(N), lo(N, m), hi(N, -1);
    for (int &x : a)
        cin >> x;
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y) {
        return a[x] < a[y];
    });
    int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    for (int j = 0; j < m; j++)
        lo[(n - 1) * m + j] = hi[(n - 1) * m + j] = j;
    for (int u : order) {
        int x = u / m, y = u % m;
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k], yy = y + dy[k];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
                int v = xx * m + yy;
                if (a[v] < a[u]) {
                    lo[u] = min(lo[u], lo[v]);
                    hi[u] = max(hi[u], hi[v]);
                }
            }
        }
    }
    vector<int> seen(N), q;
    for (int j = 0; j < m; j++) {
        seen[j] = 1;
        q.push_back(j);
    }
    for (int i = 0; i < (int)q.size(); i++) {
        int u = q[i], x = u / m, y = u % m;
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k], yy = y + dy[k];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
                int v = xx * m + yy;
                if (!seen[v] && a[v] < a[u]) {
                    seen[v] = 1;
                    q.push_back(v);
                }
            }
        }
    }
    int missing = 0;
    for (int j = 0; j < m; j++)
        missing += !seen[(n - 1) * m + j];
    if (missing) {
        cout << 0 << "\n" << missing << "\n";
        return 0;
    }
    vector<pair<int, int>> ranges;
    for (int j = 0; j < m; j++)
        if (hi[j] >= 0)
            ranges.push_back({lo[j], hi[j]});
    sort(ranges.begin(), ranges.end());
    int at = 0, i = 0, ans = 0;
    while (at < m) {
        int end = at - 1;
        while (i < (int)ranges.size() && ranges[i].first <= at) {
            end = max(end, ranges[i].second);
            i++;
        }
        ans++;
        at = end + 1;
    }
    cout << 1 << "\n" << ans << "\n";
}