思路描述来自：http://hi.baidu.com/perfectcai_/item/701f2efa460cedcb0dd1c820
也可以参考黑书P89的积水。
题意：Farmer
John有一个碗，形状如下，给你一个w*h平面，每个1*1的位置有一个高度Hij，问用这个碗来装牛奶，最多可以装多少体积。
例如：
555
515
555
这个可以装4体积，只有中间的1位置可以装；
再如：
555
512
555
这个可以装1体积，只有中间的1位置可以装，而装到2时就会开始漏出，因为液体是可以流动的；
分析：
由例子二可以很深刻的理解如果在一个桶边上打一些洞，那么之后这个桶能装的水取决于最低的那个洞的高度，
接着这个思路往下，对于最开始，只要找到这w*h外围的方格放入队列，这是最开始的边缘，取出其中最低的点x，
然后考察它周围4个位置中合法并且可以积水的点中的格子y，高度为Hy。
若y的高度大于x的高度，那么直接把Hy放入队列，并标记为禁止积水；
如果小于，把Hx放入队列，且ans+=Hx-Hy，意味着y位置可以放Hx-Hy体积的水，也标记为禁止积水。
然后再取禁止积水的格子中最低的，即队列中的最小值，继续向四周拓展。
核心思想：找最低边缘，把积过水的格子看成高度更新后的边缘。
由于要取最小高度，所以用到优先级队列，至于如何向四周扩展，我用的是bfs+dfs
#include <iostream> #include <queue> #include <stdio.h> #include <algorithm> using namespace std; const int maxn=301; int w,h; long long block[maxn][maxn]; int mark[maxn][maxn]; //标记是否可以积水 long long ans=0; struct Node{ int x,y; long long height; bool operator<(const Node tmp)const{ return height>tmp.height; } }tmp; priority_queue<Node> q; //终于知道为什么AC不了了啊，原来之前的参数height写得是h，与整个board的高度h重复了额 void dfs(int x,int y,long long height){ if(x<1||x>h||y<1||y>w) return; mark[x][y]=0; ans+=height-block[x][y]; //上 if(x-1>0&&mark[x-1][y]){ if(height>block[x-1][y]) dfs(x-1,y,height); else{ mark[x-1][y]=0; tmp.x=x-1; tmp.y=y; tmp.height=block[x-1][y]; q.push(tmp); } } //下 if(x+1<=h&&mark[x+1][y]){ if(height>block[x+1][y]) dfs(x+1,y,height); else{ mark[x+1][y]=0; tmp.x=x+1; tmp.y=y; tmp.height=block[x+1][y]; q.push(tmp); } } //左 if(y-1>0&&mark[x][y-1]){ if(height>block[x][y-1]) dfs(x,y-1,height); else{ mark[x][y-1]=0; tmp.x=x; tmp.y=y-1; tmp.height=block[x][y-1]; q.push(tmp); } } //右 if(y+1<=w&&mark[x][y+1]){ if(height>block[x][y+1]) dfs(x,y+1,height); else{ mark[x][y+1]=0; tmp.x=x; tmp.y=y+1; tmp.height=block[x][y+1]; q.push(tmp); } } } int main() { Node node; scanf("%d%d",&w,&h); for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ mark[i][j]=1; scanf("%I64d",&block[i][j]); //存储高度 if(i==1||i==h||j==1||j==w){ mark[i][j]=0; //表示禁止积水 node.x=i; node.y=j; node.height=block[i][j]; q.push(node); } } } ans=0; //bfs+dfs while(!q.empty()){ node=q.top(); q.pop(); dfs(node.x,node.y,node.height); } cout<<ans<<endl; return 0; }
下面给出只用队列+bfs的代码，速度稍慢一点：
参考链接：http://www.cnblogs.com/dongsheng/archive/2013/04/25/3043512.html
#include <iostream> #include <queue> #include <stdio.h> #include <algorithm> using namespace std; const int maxn=305; int w,h; long long block[maxn][maxn]; int mark[maxn][maxn]; int dir[4][2] = {-1,0,0,1,1,0,0,-1}; long long ans=0; struct Node { int x,y; long long h; bool operator<(const Node tmp)const { return h>tmp.h; } } tmp; priority_queue<Node> q; long long BFS() { long long ans = 0; int i, j; Node t1, t2; while(!q.empty()) { t1 = q.top(); q.pop(); for(int k = 0; k < 4; ++k) { i = t1.x + dir[k][0]; j = t1.y + dir[k][1]; if(i > 0 && i <= h && j > 0 && j <= w && mark[i][j]) { if(block[i][j] < t1.h) { ans += t1.h - block[i][j]; t2.x = i; t2.y = j; t2.h = t1.h; } else { t2.x = i; t2.y = j; t2.h = block[i][j]; } mark[i][j] = 0; q.push(t2); } } } return ans; } int main() { Node node; //cin>>w>>h; while(scanf("%d%d",&w,&h)!=EOF) { for(int i=1; i<=h; i++) { for(int j=1; j<=w; j++) { mark[i][j]=1; scanf("%I64d",&block[i][j]); if(i==1||i==h||j==1||j==w) { mark[i][j]=0; //表示禁止积水 node.x=i; node.y=j; node.h=block[i][j]; q.push(node); } } } ans=0; printf("%I64d\n",BFS()); } return 0; }