407 Trapping Rain Water II 接雨水 II

给定一个m x n的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
说明:
m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。
示例：
给出如下 3x6 的高度图:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]
返回 4。

详见：https://leetcode.com/problems/trapping-rain-water-ii/description/

C++：

class Solution {

public:

    int trapRainWater(vector<vector<int>>& heightMap) {

        if (heightMap.empty())

        {

            return 0;

        }

        int m = heightMap.size(), n = heightMap[0].size(), res = 0, mx = INT_MIN;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

        vector<vector<bool>> visited(m, vector<bool>(n, false));

        vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}};

        for (int i = 0; i < m; ++i)

        {

            for (int j = 0; j < n; ++j)

            {

                if (i == 0 || i == m - 1 || j == 0 || j == n - 1)

                {

                    q.push({heightMap[i][j], i * n + j});

                    visited[i][j] = true;

                }

            }

        }

        while (!q.empty())

        {

            auto t = q.top(); q.pop();

            int h = t.first, r = t.second / n, c = t.second % n;

            mx = max(mx, h);

            for (int i = 0; i < dir.size(); ++i)

            {

                int x = r + dir[i][0], y = c + dir[i][1];

                if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y])

                {

                    continue;

                }

                visited[x][y] = true;

                if (heightMap[x][y] < mx)

                {

                    res += mx - heightMap[x][y];

                }

                q.push({heightMap[x][y], x * n + y});

            }

        }

        return res;

    }

};

参考：https://www.cnblogs.com/grandyang/p/5928987.html

407 Trapping Rain Water II 接雨水 II的相关教程结束。