poj2227:http://poj.org/problem?id=2227
题意：给你一块矩形区域，这个矩形区域是由一个个方格拼起来的，并且每个方格有一个高度。现在给这个方格灌水，问最多能装多少水。例如
555
525
555
这个区域，只有中间的一个方格能装水，因为只有中间的高度比周围都低，所以能装3单位的水。
题解：一开始自己也不不知道怎么做，看了黑书p89的介绍才知道怎么做。是这样的，从边界周围的最低处入手，DFS，如果周围的方格比这个高度高，则把这个方格加入最小堆中，如果比这个小，则继续DFS。同时要注意边界的处理。这样一来，每次DFS，都能确定新的边界，并且每次都是从已知边界的最小处进行DFS。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int used[][];
int g[][];
long long sum,counts,counts2;
int n,m;
struct Node{
int x;
int y;
int h;
bool operator<(const Node b)const{
return h>b.h;
}
};
priority_queue<Node>Q;
void DFS(int x,int y,int h){
if(x+<n&&!used[x+][y]){
used[x+][y]=;
if(g[x+][y]>=h){
Node tt;
tt.x=x+;tt.y=y;tt.h=g[x+][y];
Q.push(tt);
}
else {
counts+=g[x+][y];
counts2++;
DFS(x+,y,h);
}
}
if(x->&&!used[x-][y]){
used[x-][y]=;
if(g[x-][y]>=h){
Node tt;
tt.x=x-;tt.y=y;tt.h=g[x-][y];
Q.push(tt);
}
else {
counts+=g[x-][y];
counts2++;
DFS(x-,y,h);
}
}
if(y+<m&&!used[x][y+]){
used[x][y+]=;
if(g[x][y+]>=h){
Node tt;
tt.x=x;tt.y=y+;tt.h=g[x][y+];
Q.push(tt);
}
else {
counts+=g[x][y+];
counts2++;
DFS(x,y+,h);
}
}
if(y->&&!used[x][y-]){
used[x][y-]=;
if(g[x][y-]>=h){
Node tt;
tt.x=x;tt.y=y-;tt.h=g[x][y-];
Q.push(tt);
}
else {
counts+=g[x][y-];
counts2++;
DFS(x,y-,h);
}
}
}
int main(){
while(~scanf("%d%d",&m,&n)){
memset(used,,sizeof(used));
sum=;
while(!Q.empty())Q.pop();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
scanf("%d",&g[i][j]);
if(i==||i==n||j==||j==m){
Node tt;
tt.x=i;tt.y=j;tt.h=g[i][j];
Q.push(tt);
}
}
while(!Q.empty()){
Node ttt=Q.top();
Q.pop();
int xxx=ttt.x;
int yyy=ttt.y;
int hhh=ttt.h;
counts=;counts2=;
used[xxx][yyy]=;
DFS(xxx,yyy,hhh);
sum+=counts2*hhh-counts;
}
printf("%I64d\n",sum);
}
}