题目描述

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:

Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

题意：给定一个 m x n 的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

说明:m 和 n都是小于110的整数。每一个单位的高度都大于 0 且小于 20000。

算法1

(堆)

这是Trapping Rain Water（Leetcode 42题）的二维版本。在一维版本中，限制每个位置能够接的雨水量是左右两侧最大值的最小值，因此只需要两遍扫描就可以解决，单调栈可以一次扫描便解决。

到这一题，如果我们直接套用那一题的做法，即每个位置接的雨水量是上下左右四个方向最大值的最小值的话，就会得到错误的解法，这是因为，假设当前位置右边位置高度小于当前位置，那么当前位置的水会流向右边位置从而受到右边位置能够接的雨水量的影响。

首先我们可以明确所有边界上的点都不能够接到水，初始边界就是矩形的边界，然后我们不断的收缩这个边界。先把最外围的一圈作为围栏， 选择一个最低的围栏， 如果这个围栏的邻节点都比它大， 此围栏可删除，邻节点作为新的围栏； 如果邻节点比它小， 那么邻节点可储蓄的水为二者高度之差， 此时在邻节点设置围栏，高度为当前围栏高度即可。

对于这一题，我们的解题思路如下：

1. 首先排除不合法的值，只有当且仅当n > 2 and m > 2的时候才可能有最优解。
2. 我们先将所有边界上的点加入一个关于对应位置高度的小顶堆，为了记录位置，我们使用一个pair<height[x][y],x * m + y>来记录对应的高度和位置，我们使用cur_max记录当前已经出堆的点中最大值。
3. 我们每次从堆顶取出一个位置，同时更新最大值cur_max，接下来遍历当前位置相邻的并且还没有被访问过的位置加入队列，如果其高度小于cur_max，那么我们更新答案res += cur_max - height[x][y]。
4. 重复3，直至堆为空。

动态过程可以看这个链接的解释：https://www.youtube.com/watch?v=cJayBq38VYw

    int trapRainWater(vector<vector<int>>& heightMap) {
        if(heightMap.empty()) return 0;
        int n = heightMap.size(),m = heightMap[0].size(),cur_max = INT_MIN,res = 0;
        if(n <= 2 || m <= 2) return 0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > heap;
        for(int i = 0 ; i < n ; i ++)
        {
            heap.push(make_pair(heightMap[i][0],i * m));
            heap.push(make_pair(heightMap[i][m - 1],i * m + m - 1));
        }
        for(int j = 1 ; j < m - 1 ; j ++)
        {
            heap.push(make_pair(heightMap[0][j],j));
            heap.push(make_pair(heightMap[n - 1][j],(n - 1) * m + j));
        }
        int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1},visit[n][m] = {};
        while(!heap.empty())
        {
            auto t = heap.top();
            heap.pop();
            cur_max = max(cur_max,t.first);
            int r = t.second / m,c = t.second % m;
            for(int i = 0 ; i < 4 ; i ++)
            {
                int x = r + dx[i],y = c + dy[i];
                if(x > 0 && x < n - 1 && y > 0 && y < m - 1 && visit[x][y] == 0)
                {
                    visit[x][y] = 1;
                    if(heightMap[x][y] < cur_max)
                        res += cur_max - heightMap[x][y];
                    heap.push(make_pair(heightMap[x][y],x * m + y));
                }
            }
        }
        return res;
    }