[文章目录]
Description
约翰的奶牛们找到了一份不错的兼职一设计冲压式榨汁机．榨汁机设计如下：
一个W* H的底座(3≤W,H≤300) 每一个1 *1的方格上都放有一个高度为B(1≤B≤109)的柱予，用来榨汁．假设柱子之间都被完美地粘合了，这样水不会顺着柱子与柱子之间的空隙流走．但是约翰一直不知道，这么一个榨汁机，到底能装多少果汁？假设榨汁机周围没有任何东西，也就是说，边界上的水都会流走，有些榨汁机则根本不能装下任何的果汁．
搜索出当前不能有水的位置。将高度从小到大排序，枚举位置，如果当前高度为一个边界（周围存在可以有水的位置），该高度即为水的高度，进行搜索灌水，灌到的位置相当于新的不能有水的位置。时间复杂度O(n*m*log(n*m))
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int lim; ll ans;
int m,n,h[310][310];
bool bor[310][310],vis[310][310];
void dfs_bor(int x,int y)
{
if(bor[x][y]) return ;
bor[x][y]=1;
if(x!=1&&h[x-1][y]>=h[x][y]) dfs_bor(x-1,y);
if(y!=1&&h[x][y-1]>=h[x][y]) dfs_bor(x,y-1);
if(x!=n&&h[x+1][y]>=h[x][y]) dfs_bor(x+1,y);
if(y!=m&&h[x][y+1]>=h[x][y]) dfs_bor(x,y+1);
}
int tot;
struct node
{
int x,y,w;
}a[310*310];
bool cmp(node x,node y){return x.w<y.w;}
void dfs(int x,int y)
{
bor[x][y]=1;
if(h[x][y]<=lim)
{
ans+=lim-h[x][y];
if(x!=1&&!bor[x-1][y]) dfs(x-1,y);
if(x!=n&&!bor[x+1][y]) dfs(x+1,y);
if(y!=1&&!bor[x][y-1]) dfs(x,y-1);
if(y!=m&&!bor[x][y+1]) dfs(x,y+1);
}
}
void work(int x,int y)
{
if(!bor[x][y]) return ; lim=h[x][y];
if(x!=1&&!bor[x-1][y]) dfs(x-1,y);
if(x!=n&&!bor[x+1][y]) dfs(x+1,y);
if(y!=1&&!bor[x][y-1]) dfs(x,y-1);
if(y!=m&&!bor[x][y+1]) dfs(x,y+1);
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
scanf("%d",&h[i][j]);
a[++tot].x=i; a[tot].y=j; a[tot].w=h[i][j];
}
sort(a+1,a+tot+1,cmp);
for(int i=1;i<=m;++i)
{
if(!bor[1][i]) dfs_bor(1,i);
if(!bor[n][i]) dfs_bor(n,i);
}
for(int i=1;i<=n;++i)
{
if(!bor[i][1]) dfs_bor(i,1);
if(!bor[i][m]) dfs_bor(i,m);
}
for(int i=1;i<=tot;++i)
work(a[i].x,a[i].y);
printf("%lld",ans);
return 0;
}