PBCWATER - Tính toán lượng nước
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxs 10000
#define maxn 110
#define fr(a,b,c) for(a=b;a<=c;a++)
#define frr(a,b,c) for(a=b;a>=c;a--)
using namespace std;
const int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n,m,a[maxn][maxn],qx[maxs+10],qy[maxs+10],q,d[maxn][maxn];
int p[maxs+10],px[maxs+10],py[maxs+10],l[maxs+10];
long long re;
void bfs(int x,int y,int val)
{
int i,j;
d[x][y]=val; qx[1]=x; qy[1]=y; i=q=1;
while (i<=q)
{
x=qx[i]; y=qy[i++];
fr(j,0,3)
{
int xx=x+dx[j],yy=y+dy[j];
if (!d[xx][yy] && a[xx][yy]<=val)
{
d[xx][yy]=val;
qx[++q]=xx; qy[q]=yy;
}
}
}
}
int border(int x,int y)
{
int i;
fr(i,0,3)
if (d[x+dx[i]][y+dy[i]]) return 1;
return 0;
}
int main()
{
int i,j,x,y;
scanf("%d%d",&m,&n);
fr(i,1,m)
fr(j,1,n)
{
scanf("%d",&a[i][j]);
p[a[i][j]]++;
}
fr(i,2,maxs+1) p[i]+=p[i-1];
fr(i,1,m)
fr(j,1,n)
{
px[p[a[i][j]]]=i; py[p[a[i][j]]--]=j;
}
fr(i,1,m) d[i][0]=d[i][n+1]=-1;
fr(i,1,n) d[0][i]=d[m+1][i]=-1;
fr(i,1,m*n)
{
x=px[i]; y=py[i];
if (!d[x][y] && border(x,y)) bfs(x,y,a[x][y]);
}
fr(i,2,m-1)
fr(j,2,n-1)
re+=max(0,d[i][j]-a[i][j]);
cout << re << endl;
return 0;
}