Poj2227题解水库体积

题目链接

题目：已知有一个W×H面积大小的水库，里面由W×H个1×1大小的砖块构成，每个砖块的高度为 H.求该水库最多能储存多少单位的水？

如何计算体积？

短板效应：一个1×1的区域内最多存储多少水取决于它所在边界中最矮的那一块板子

拿3×3的方格举例：只有最中间(坐标为(2,2) )的方格能储存水，且体积大小 $ V=1×1×(H_{边界中最矮} - H_{2，2}) $

• 推论：一个砖块能存储的体积，只与离他最近周围四个砖块高度有关

思路：考虑将一个一个单位的砖块相加即为最终体积
首先将水库最外围的每个砖块按高度由矮到高排序（优先队列 $ O(logn) $）

每次弹出当前最矮的砖块，搜索周围四个坐标。

• 如果坐标的高度大于等于边界高度，则无法蓄水，该坐标成为新的边界加入队列
• 如果坐标的高度小于边界高度，则可以蓄水 $ H_{边界} - H_{x,y} $, 将该坐标的高度改为边界的高度，成为新的边界加入队列

代码：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

#define N 100000
struct Node
{
    int x;
    int y;
    int h;
    bool operator < (const Node x)const
    {
        return h>x.h;
    }
};
int f[303][303];  //记录每个坐标的高度
int w,h;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int ans;
priority_queue<Node> q;
int main()
{
    cin>>w>>h;
    int vis[303][303]={};
    int count=0;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>f[i][j];
            Node tmp;
            if(i==1||i==h||j==1||j==w)
            {
                Node tmp;
                tmp.x=i;
                tmp.y=j;
                tmp.h=f[i][j];
                q.push(tmp);      //队列中存储的是每次判断依赖的边界
                vis[i][j]=1;       //进入队列的就标记，后续计算面积时，不需要再加入了
            }
            
            
        }
    }


    while(!q.empty())
    {
        Node edge=q.top();  
        q.pop();
        for(int i=0;i<4;i++) //四个方向搜索
        {
            int nx=edge.x+d[i][0];  
            int ny=edge.y+d[i][1];
            if(vis[nx][ny]==0&&nx>=1&&nx<=h&&ny>=1&&ny<=w)
            {
                if(f[nx][ny]>=edge.h)  //如果当前砖块的高度大于等于边界，则无法蓄水，且会成为新的边界
                {
                    vis[nx][ny]=1;
                    Node tmp;
                    tmp.x=nx;
                    tmp.y=ny;
                    tmp.h=f[nx][ny];  //将该位置的边界高度更改
                    q.push(tmp);
                }
                else        //如果当前砖块的高度小于边界，则可以蓄水，更新的边界高度不变
                { 
                    vis[nx][ny]=1;
                    ans+=edge.h-f[nx][ny];
                    Node tmp;
                    tmp.x=nx;
                    tmp.y=ny;
                    tmp.h=edge.h;
                    q.push(tmp);

                }
            }
        }
        
    }
    cout<<ans<<endl;
    

}