【牛客】用水填坑 （优先队列）

由外向内去计算每一点能积累水的体积，一点处的水的体积取决于这一点和其四周的高度，用优先队列维护当前更新的点，每次取出高度最低的点，去更新其四周的点，再将四周的点放入队列

最后答案就是每一点更新后与原来的高度差总和

#include <bits/stdc++.h>
using namespace std;
#define mset(var,val) memset(var,val,sizeof(var))
#define rep(i,x,n) for(int i=x;i<n;i++)
#define rep1(i,x,n) for(int i=x;i<=n;i++)
#define lowbit(x) (x&-x)
#define ls(i) i<<1
#define rs(i) i<<1|1
#define fr first
#define sc second
typedef long long int lli;
typedef unsigned long long ull;
const ull base=131;
//const long long int INF=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const long double eps=1e-20;
const int mod=998244353;
const int M=1e4+10;
int n,m,a[M][M],b[M][M],vis[M][M],dir[4][2]={-1,0,1,0,0,1,0,-1};
lli ans;
struct d
{
    int x,y,h;
    d(int xx,int yy,int hh){x=xx;y=yy;h=hh;}
    bool operator <(const d &a)const
    {
        return h>a.h;
    }
};
priority_queue<d> pq;
int main(int argc, char const *argv[])
{
    scanf("%d%d",&n,&m);
    rep1(i,1,n)rep1(j,1,m)
    {
        scanf("%d",&a[i][j]);
        b[i][j]=a[i][j];
        if(i==1||i==n||j==1||j==m)
        {
            vis[i][j]=1;
            pq.push(d(i,j,b[i][j]));
        }
    }
    while(!pq.empty())
    {
        d now=pq.top();pq.pop();
        rep(i,0,4)
        {
            int xx=now.x+dir[i][0];
            int yy=now.y+dir[i][1];
            if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy])continue;
            vis[xx][yy]=1;
            b[xx][yy]=max(b[xx][yy],now.h);
            pq.push(d(xx,yy,b[xx][yy]));
        }
    }
    rep1(i,1,n)rep1(j,1,m)ans+=b[i][j]-a[i][j];
    printf("%lld\n",ans);
 return 0;
}
//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);