poj2227:http://poj.org/problem?id=2227
题意：给你一块矩形区域，这个矩形区域是由一个个方格拼起来的，并且每个方格有一个高度。现在给这个方格灌水，问最多能装多少水。例如
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\n",sum); 100 } 101 }