NC21166. 用水填坑
描述
输入描述
第一行两个数 n, m，具体含义见题意接下来 n 行每行 m 个数, 第 i 行为 hi,1, hi,2, ..., hi,m
输出描述
输出一行一个数表示积水的总量
示例1
输入:
5 5 0 0 5 0 0 0 4 3 8 2 9 5 7 2 7 1 9 6 5 4 1 0 0 6 2
输出:
4
示例2
输入:
10 10 0 0 0 0 0 0 0 0 0 0 0 5 2 6 4 3 1 7 8 0 0 6 4 2 3 5 1 4 6 0 0 3 6 4 1 2 4 7 8 0 0 2 5 5 1 2 3 4 4 0 0 2 3 1 5 4 4 1 4 0 0 4 1 2 3 4 5 2 1 0 0 7 5 5 1 5 4 5 7 0 0 1 3 5 5 4 6 8 7 0 0 0 0 0 0 0 0 0 0 0
输出:
23
C++11(clang++ 3.9) 解法, 执行用时: 496ms, 内存消耗: 24144K, 提交时间: 2019-03-29 20:40:29
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct node{int x,y,h;};
int n,m,a[N][N],vis[N][N],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
long long ans;
bool operator<(node a,node b){return a.h>b.h;}
priority_queue<node>q;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&a[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(i==1||j==1||i==n||j==m)q.push((node){i,j,a[i][j]}),vis[i][j]=1;
while(!q.empty())
{
node u=q.top();q.pop();
for(int k=0;k<4;k++)
{
int x=u.x+dx[k],y=u.y+dy[k];
if(x<1||x>n||y<1||y>m||vis[x][y])continue;
vis[x][y]=1;
if(a[x][y]<u.h)ans+=u.h-a[x][y],a[x][y]=u.h;
q.push((node){x,y,a[x][y]});
}
}
printf("%lld",ans);
}