一道ACM题
题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2235
这道题是我想了很久，但还是一点思路都没有，有兴趣的朋友一起来思考一下吧。
先谢谢了。
[解决办法]
帮顶。
很有意思的一道题目。
或许可以先找到所有连通的0区域，
然后检测这些区域的边界，找到最小高度。。。
[解决办法]
挺有意思的
我觉得关键在于找水位。鉴于容器里的水可以分成水位不同的若干区域，程序的难点在于怎么高效的分割这些区域，找出各自的水位，有了水位就可以计算容积了
实现起来可能比较麻烦一点，尤其是对比较变态一点的输入，要考虑周全
[解决办法]
0- int sum=0
1-按高度排序h0< h1 < h2 < ... < hn
2-从外围向内搜索，如果最外围存在h0，那么这种格子势必不能蓄水，高度标记为-1
3-然后向内搜索，所有与前面高度为-1相邻并且高度为h0的格子，都将高度标记为-1
4-剩下没有标记为-1的高度为h0的格子的个数为k0，sum+=(h1-h0)*k0，并将它们高度标记为h1
5-将h1当做h0，跳回步骤2
[解决办法]
这类题目，应该从堆的操作来想...
[解决办法]
AC了。 218MS
2330994 2010-04-12 14:46:54 Accepted 2235 218MS 2176K 2397 B G++
其实也没用什么高深算法，就是写了个BFS。
每次寻找一个点，若该点的高度 <= 其周围的点的高度，则进入BFS。
由BFS扩展出所有与该点相同高度的点，并记录其周围高出来的最低点。
然后将这些扩展出来的点提升为新的高度，并更新最终容量。
直到容量不再可更新，就可以退出循环了。
代码也并不难写，不过还是WA了几次。。。。。。
主要一点，就是循环的写法，不应该每次循环只扩展一次容量就跳出循环重来，而应该在一次循环中尽可能多的进行扩展，不然会TLE。。。（刚试了）
代码（风格不好，见笑了)：
#include <stdio.h>#include <string.h>#define MAXN 510#define add(a, b) if (h[a][b] > high) {\ if (min > h[a][b])\ min = h[a][b];\ } else if (h[a][b] < high || flag[a][b] && flag[a][b] != BFS_TIMES) {\ overflow = true;\ } else if (!flag[a][b] && h[a][b] == high) {\ if (a == 0 || b == 0 || a >= n-1 || b>= m-1)\ overflow = true;\ else {\ flag[a][b] = BFS_TIMES;\ list[tot].x=a;\ list[tot++].y=b;\ }\ }int n, m, t, ans;int h[MAXN][MAXN];int flag[MAXN][MAXN];int BFS(int x, int y){ static struct{ int x, y; }list[MAXN * MAXN]; static int BFS_TIMES = 0; BFS_TIMES++; int tot; tot = 1; list[0].x = x; list[0].y = y; flag[x][y] = BFS_TIMES; int i, high; int min = 0x7FFFFFFF; high = h[x][y]; bool overflow = false; for (i=0; i<tot; ++i) { x = list[i].x; y = list[i].y; add(x-1, y); add(x+1, y); add(x, y-1); add(x, y+1); } if (overflow){ // 溢出 return 0; } for (i=0; i<tot; ++i){ h[list[i].x][list[i].y] = min; // 将填充的格子的高度提上来 flag[list[i].x][list[i].y] = 0; // flag 还原 } return (min - high) * tot;;}int main(){ int i, j, k; bool found; scanf("%d", &t); while (t--) { scanf("%d %d", &n, &m); for (i=0; i<n; ++i) for (j=0; j<m; ++j) scanf("%d", &h[i][j]); ans = 0; do{ found = false; memset(flag, 0, sizeof flag); for (i=1; i<n-1; ++i) for (j=1; j<m-1; ++j) if (!flag[i][j] && h[i][j] <= h[i-1][j] && h[i][j] <= h[i+1][j] && h[i][j] <= h[i][j-1] && h[i][j] <= h[i][j+1]) { k = BFS(i,j); if (k){ found = true; ans += k; } } } while (found); printf("%d\n", ans); }}