(并查集) $O(n \times m + V)$

这题是POI1999原题，也就是BZOJ2936。

由于数值的范围在20000以内，可以用并查集搞。

把要流出去的点和n * m相连。从0到最高点，依次考虑每个高度。

假设当前考虑到高度为v的方块，枚举所有高度为v的方块，计算有多少个v的块可以填一个高度的水。

由于所以低于这个方块的都已经考虑过，直接看周围是否有已经vis过的方块，然后把他们和当前块连起来，表示往当前块上放水会流向这些块。

对于这一层的答案，就是高度为v的块 - 要流出去的块。

比$nmlogn$的做法要快一些。

C++ 代码

class Solution {
public:
    int fa[120 * 120], vis[120 * 120], sz[120 * 120];
    int n, m;
    int find(int x)
    {
        if(fa[x] == x ) return x;
        return fa[x] = find(fa[x]);
    }
    bool check(int x, int y)
    {
        if(x < 0 || x >= n || y < 0 || y >= m) return 0;
        return 1;
    }
    int trapRainWater(vector<vector<int>>& heightMap) {
        n = heightMap.size(), m = heightMap[0].size();
        for(int i = 0; i <= n * m; i++) fa[i] = i, sz[i] = 1;
        sz[n * m ] = 0;
        memset(vis, 0, sizeof vis);
        int V = 0;
        vector<int> pii[20010];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) 
                pii[heightMap[i][j]].push_back(i * m + j),
                V = V < heightMap[i][j] ? heightMap[i][j]: V;
        int cnt = 0, res = 0;
        int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int v = 0; v < V; v++)
        {
            for(int i = 0; i < pii[v].size(); i++)
            {
                cnt++;
                int x = pii[v][i] / m, y = pii[v][i] % m;
                vis[x * m + y] = 1;
                for(int k = 0; k < 4; k++)
                {
                    int dx = x + dir[k][0], dy = y + dir[k][1];
                    int flag = 0;
                    if(!check(dx, dy) || vis[dx * m + dy]) 
                    {
                        int fx, fy;
                        if(!check(dx, dy)) fx = find(n * m);
                        else fx = find(dx * m + dy);
                        fy = find(x * m + y);
                        if(fx == fy) continue;
                        sz[fx] += sz[fy];
                        fa[fy] = fx;
                    }
                }
            }
            // cout << cnt << endl;
            res += cnt - sz[find(n * m)];
        }
        return res;
    }
};