The Wedding Juicer POJ - 2227

采取从外层边界，一步一步向内部拓展的策略，具体来说，一开始将最外面一层的点加入队列，并标记这些点的坐标已经被访问

取出队列中高度最低的点，将其弹出，查看其上下左右的点，如果新点没有被访问过，分两种情况：
1.如果新点的高度大于等于当前点：将新点加入队列，标记新点已经访问过了，该点无法储水

2.如果新点的高度小于当前点：则新点储水（当前点的高度 - 新点的高度），首先，这么多水一定可以存，因为当前点的高度是边界高度中最小的，其次，这是能存的最多的水，因为再多就超过了当前点高度，所以这个点能储存的水，在这种策略下，是所求的最大解，将储水结果累加进ans，并且将这个新点的高度改成当前点的高度后，标记新点坐标已访问，将新点加入队列中

不断重复以上操作，直到队列为空

复杂度略

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;#define ll long longconst ll maxn=305;
ll w,h,ans;
ll a[maxn][maxn],vis[maxn][maxn];
ll dx[]={-1,1,0,0},dy[]={0,0,-1,1};struct node{ll x,y,h;node(ll x=0,ll y=0,ll h=0):x(x),y(y),h(h) {}bool operator < (const node &rhs) const {return h>rhs.h;}
};int main()
{ios::sync_with_stdio(0);cin.tie(0);cin>>w>>h;for(ll i=1;i<=h;i++){for(ll j=1;j<=w;j++){cin>>a[i][j];}}priority_queue<node> q;//将最外一层加入队列for(int i=1;i<=w;i++){if(vis[1][i]==0) {vis[1][i]=1;q.push(node(1,i,a[1][i]));}if(vis[h][i]==0) {vis[h][i]=1;q.push(node(h,i,a[h][i]));}}for(int i=1;i<=h;i++){if(vis[i][1]==0){vis[i][1]=1;q.push(node(i,1,a[i][1]));}if(vis[i][w]==0){vis[i][w]=1;q.push(node(i,w,a[i][w]));}}/*while(q.size()){node t=q.top();q.pop();printf("(%lld,%lld)\n",t.x,t.y);}*/while(q.size()){node t=q.top();q.pop();ll x=t.x,y=t.y,h1=t.h;for(ll i=0;i<4;i++){ll nx=x+dx[i],ny=y+dy[i];if(nx<1 || nx>h || ny<1 || ny>w) continue;if(vis[nx][ny]) continue;if(a[nx][ny]>=h1) {q.push(node(nx,ny,a[nx][ny]));vis[nx][ny]=1;}else {ans+=h1-a[nx][ny];q.push(node(nx,ny,h1));vis[nx][ny]=1;}}}cout<<ans<<"\n";return 0;
}