poj 2227 The Wedding Juicer

Farmer John's cows have taken a side job designing interesting punch-bowl designs. The designs are created as follows: * A flat board of size W cm x H cm is procured (3 <= W <= 300, 3 <= H <= 300) * On every 1 cm x 1 cm square of the board, a 1 cm x 1 cm block is placed. This block has some integer height B (1 <= B <= 1,000,000,000) The blocks are all glued together carefully so that punch will not drain through them. They are glued so well, in fact, that the corner blocks really don't matter! FJ's cows can never figure out, however, just how much punch their bowl designs will hold. Presuming the bowl is freestanding (i.e., no special walls around the bowl), calculate how much juice the bowl can hold. Some juice bowls, of course, leak out all the juice on the edges and will hold 0.

Input

* Line 1: Two space-separated integers, W and H * Lines 2..H+1: Line i+1 contains row i of bowl heights: W space-separated integers each of which represents the height B of a square in the bowl. The first integer is the height of column 1, the second integers is the height of column 2, and so on.

Output

* Line 1: A single integer that is the number of cc's the described bowl will hold.

Sample Input

4 5 5 8 7 7 5 2 1 5 7 1 7 1 8 9 6 9 9 8 9 9

Sample Output

12

【题意】

给你一个图，图中每个点有个柱子，柱子的高可能不相等，让你往柱子里面加水，但是水不能溢出来，问你能加的最大水量是多少。

【分析】

首先，边界上是一定不能加水的，所以只能是往中间加。所以我们直接维护一个优先队列，让里面放边界值，然后不断的往里面收缩，如果里面的柱子比外面的低就加水，修改边界，一直重复下去，直到搜索到了所有的柱子为止。然后统计答案就行了。

【代码】

#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> #include<sstream> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define sin(a) scanf("%d",&(a)) #define sin2(a,b) scanf("%d%d",&(a),&(b)) #define sll(a) scanf("%lld",&(a)) #define sll2(a,b) scanf("%lld%lld",&(a),&(b)) #define sdo(a) scanf("%lf",&(a)) #define sdo2(a,b) scanf("%lf%lf",&(a),&(b)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef pair<int,int> PII; #define A first #define B second #define pb push_back #define MK make_pair #define ll long long template<typename T> void read1(T &m) { T x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } m = x*f; } template<typename T> void read2(T &a,T &b) { read1(a); read1(b); } template<typename T> void read3(T &a,T &b,T &c) { read1(a); read1(b); read1(c); } template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } template<typename T> void outn(T a) { if(a>9) out(a/10); putchar(a%10+'0'); puts(""); } using namespace std; int lenx,leny; typedef struct poi { int value; int x,y; poi() {} poi(int _v,int _x,int _y):value(_v),x(_x),y(_y) {} } P; bool operator< (P a,P b) { return a.value>b.value; } P a,b; int changex[]={0,0,1,-1}; int changey[]={1,-1,0,0}; int mat[305][305]; int vis[305][305]; priority_queue<P>x; bool cal(int x,int y) { if(x<0||x>=lenx) return false; if(y<0||y>=leny) return false; if(vis[x][y]) return false; return true; } int main() { // freopen("in.txt","r",stdin); read2(leny,lenx); memset(vis,false,sizeof(vis)); for(int i=0; i<lenx; i++) for(int j=0; j<leny; j++) { read1(mat[i][j]); if(i==0||i==lenx-1||j==0||j==leny-1) { x.push(poi(mat[i][j],i,j));//先把所有的边界压进去 vis[i][j]=true; } } int ans=0; while(!x.empty()) { a=x.top(); x.pop(); for(int i=0;i<4;i++) { b.x=a.x+changex[i]; b.y=a.y+changey[i]; if(cal(b.x,b.y)) { b.value=mat[b.x][b.y]; if(b.value<a.value) ans+=a.value-b.value,b.value=a.value; mat[b.x][b.y]=b.value; vis[b.x][b.y]=true; x.push(b); } } } outn(ans); return 0; }