一道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。。。（刚试了）

代码（风格不好，见笑了)：

C/C++ code

#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);    }}