The Wedding Juicer

题意：给你一块矩形区域，这个矩形区域是由一个个方格拼起来的，并且每个方格有一个高度。现在给这个方格灌水，问最多能装多少水。例如
555
525
555
这个区域，只有中间的一个方格能装水，因为只有中间的高度比周围都低，所以能装3单位的水。
题解：一开始自己也不不知道怎么做，看了黑书p89的介绍才知道怎么做。是这样的，从边界周围的最低处入手，DFS，如果周围的方格比这个高度高，则把这个方格加入最小堆中，如果比这个小，则继续DFS。同时要注意边界的处理。这样一来，每次DFS，都能确定新的边界，并且每次都是从已知边界的最小处进行DFS。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 int used[302][302];
  8 int g[302][302];
  9 long long sum,counts,counts2;
 10 int n,m;
 11 struct Node{
 12   int x;
 13   int y;
 14   int h;
 15   bool operator<(const Node b)const{
 16     return h>b.h;
 17   }
 18 };
 19 priority_queue<Node>Q;
 20 void DFS(int x,int y,int h){
 21     if(x+1<n&&!used[x+1][y]){
 22             used[x+1][y]=1;
 23         if(g[x+1][y]>=h){
 24             Node tt;
 25             tt.x=x+1;tt.y=y;tt.h=g[x+1][y];
 26             Q.push(tt);
 27         }
 28         else {
 29             counts+=g[x+1][y];
 30             counts2++;
 31             DFS(x+1,y,h);
 32         }
 33     }
 34      if(x-1>1&&!used[x-1][y]){
 35             used[x-1][y]=1;
 36         if(g[x-1][y]>=h){
 37             Node tt;
 38             tt.x=x-1;tt.y=y;tt.h=g[x-1][y];
 39             Q.push(tt);
 40         }
 41         else {
 42             counts+=g[x-1][y];
 43             counts2++;
 44             DFS(x-1,y,h);
 45         }
 46     }
 47      if(y+1<m&&!used[x][y+1]){
 48             used[x][y+1]=1;
 49         if(g[x][y+1]>=h){
 50             Node tt;
 51             tt.x=x;tt.y=y+1;tt.h=g[x][y+1];
 52             Q.push(tt);
 53         }
 54         else {
 55             counts+=g[x][y+1];
 56             counts2++;
 57             DFS(x,y+1,h);
 58         }
 59     }
 60      if(y-1>1&&!used[x][y-1]){
 61             used[x][y-1]=1;
 62         if(g[x][y-1]>=h){
 63             Node tt;
 64             tt.x=x;tt.y=y-1;tt.h=g[x][y-1];
 65             Q.push(tt);
 66         }
 67         else {
 68             counts+=g[x][y-1];
 69             counts2++;
 70             DFS(x,y-1,h);
 71         }
 72     }
 73 }
 74 int main(){
 75 while(~scanf("%d%d",&m,&n)){
 76         memset(used,0,sizeof(used));
 77         sum=0;
 78        while(!Q.empty())Q.pop();
 79     for(int i=1;i<=n;i++)
 80         for(int j=1;j<=m;j++){
 81              scanf("%d",&g[i][j]);
 82            if(i==1||i==n||j==1||j==m){
 83                Node tt;
 84                tt.x=i;tt.y=j;tt.h=g[i][j];
 85                Q.push(tt);
 86            }
 87         }
 88        while(!Q.empty()){
 89          Node ttt=Q.top();
 90          Q.pop();
 91          int xxx=ttt.x;
 92          int yyy=ttt.y;
 93          int hhh=ttt.h;
 94          counts=0;counts2=0;
 95          used[xxx][yyy]=1;
 96          DFS(xxx,yyy,hhh);
 97          sum+=counts2*hhh-counts;
 98     }
 99     printf("%I64d
",sum);
100     }
101 }

View Code