RE求调
查看原帖
RE求调
1191129
canduanqi楼主2024/8/10 17:50
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vc vector
#define pq priority_queue
#define pb push_back

const int N = 1e6 + 10, M = 1010;
int ans = 0;
struct xx
{
    int i, j, h;
} a[N];
int b[M][M];
short c[M][M]; // 高度 是否淹没
int cmp(xx a, xx b)
{
    return a.h < b.h;
}
void dfs(int i, int j, int x)
{
    if (c[i][j - 1] || c[i][j + 1] || c[i - 1][j] || c[i + 1][j])
    {
        c[i][j] = 1;
        ans--;
        // cout << i << ' ' << j << endl;
    }
    if (b[i][j - 1] != 0 && b[i][j - 1] <= x && c[i][j - 1] == 0)
        dfs(i, j - 1, x);
    if (b[i][j + 1] != 0 && b[i][j + 1] <= x && c[i][j + 1] == 0)
        dfs(i, j + 1, x);
    if (b[i - 1][j] != 0 && b[i - 1][j] <= x && c[i - 1][j] == 0)
        dfs(i - 1, j, x);
    if (b[i + 1][j] != 0 && b[i + 1][j] <= x && c[i + 1][j] == 0)
        dfs(i + 1, j, x);
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    ans = n * m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int t;
            cin >> t;
            b[i][j] = t;
            int cnt = (i - 1) * m + j;
            a[cnt].h = t;
            a[cnt].i = i;
            a[cnt].j = j;
        }
    }
    for (int i = 0; i <= n + 1; i++)
        c[i][0] = 1, c[i][m + 1] = 1;
    for (int j = 0; j <= m + 1; j++)
        c[0][j] = 1, c[n + 1][j] = 1;
    sort(a + 1, a + n * m + 1, cmp);
    int j = 1;
    for (int i = 1; i <= q; i++)
    {
        while (a[j].h <= i && j <= n * m)
        {
            if (c[a[j].i][a[j].j] == 0)
                dfs(a[j].i, a[j].j, i);
            j++;
        }
        cout << ans << endl;
        // cout << "????" << i << endl;
    }
    return 0;
}
2024/8/10 17:50
加载中...