1 条题解

  • 0
    @ 2026-9-25 0:22:06

    按高度从小到大地顺序考虑每个位置,用并查集维护连通性。具体来讲,假设当前考虑到的高度为 hh,对每个取出来的位置,其相邻位置如果高度不超过 hh 或者是外界(简单起见,把外界也看成一个结点)就合并连通块。

    这样一来,所有高度 ≤h\le h 且不与外界相邻的位置都是可以继续积水的(至少增加 11),因为其四周肯定有比他高的位置会阻挡。具体实现见代码。

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int INF = 0x3f3f3f3f;
    const LL mod = 1e9 + 7;
    const int N = 10005;
    
    int a[105][105];
    vector<int> b[N];
    int p[N];
    int sz[N];
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int find(int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    void Union(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) {
            p[x] = y;
            sz[y] += sz[x];
        }
    }
    int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &a[i][j]);
                b[a[i][j]].push_back(i * m + j);
            }
        }
        for (int i = 0; i <= n * m; i++) {
            p[i] = i;
            sz[i] = 1;
        }
        sz[n * m] = 0;
        int ans = 0;
        int cnt = 0;
        for (int i = 1; i <= 10000; i++) {
            for (auto t : b[i]) {
                int x = t / m, y = t % m;
                cnt++;
                for (int j = 0; j < 4; j++) {
                    int tx = x + dx[j];
                    int ty = y + dy[j];
                    if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
                        if (a[tx][ty] <= a[x][y]) Union(t, tx * m + ty);
                    } else {
                        Union(t, n * m);
                    }
                }
            }
            ans += cnt - sz[find(n * m)];
        }
        cout << ans << endl;
        return 0;
    }
    
    
    • 1

    信息

    ID
    4601
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者