接雨水问题

1.一维接雨水
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        int n = height.size();
        vector<int> left(n);
        vector<int> right(n);

        left[0] = height[0], right[n - 1] = height[n - 1];
        for (int i = 1; i < n; ++i) left[i] = max(left[ i - 1], height[i]);
        for (int i = n - 2; i >= 0; --i) right[i] = max(right[i + 1], height[i]);

        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            ans += min(left[i], right[i]) - height[i];
        }
        return ans;
    }
};

2.二维接雨水
海里有一个小岛。
岛可以描述为一个具有 R 行 C 列的矩阵，其中包含的数字 H[i][j] 表示每个单元格的高度。
以下是一个 3×3 岛屿的示例：
3 5 5
5 4 5
5 5 5
有时，大雨会在这个岛上的每个单元格上均匀地降落。你可以假设降水量可以是无限大。在这样的大雨之后，岛上的一些区域（由沿着边缘连接的一个或多个单元格形成）可能会存在积水。一片区域可以存在积水的前提是与该区域内单元格沿着边缘连接的区域外的单元格的高度均高于区域内单元格。（周围的海洋被视为高度为 0 的无限单元格。）否则，水将始终流入其他区域并最终出海。你可以假设海的高度永远不会改变。在大雨过后，我们将使用 W[i][j] 来表示岛屿上每个单元格的高度。以下是对大雨过后的示例岛屿的高度的分析。
最中央的初始高度为 4 的单元格被初始高度为 5 的单元格包围着，因此在该单元格将产生积水，在积水高度到达 5 以后，没有更多区域被高度更高的单元格包围，因此将不再继续积水。
请注意，水不会直接在两个共享顶点的单元格之间流动;水必须沿着共同的边缘流动。（所以中央单元格的积水不会从左上角处流走）
以下是雨后示例岛屿的高度：
3 5 5
5 5 5
5 5 5
给定岛的高度矩阵，你能计算出大雨后的每个单元格的增加高度（W[i][j]−H[i][j]）的总和吗？
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 R 和 C。
接下来 R 行每行包含 C 个整数 H[i][j]，表示矩阵内单元格的高度。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: y，其中 x 是组别编号（从 1 开始），y 是增加高度的总和。
数据范围
1≤T≤100,
1≤H[i][j]≤1000,
1≤R,C≤50

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 55;
int n, m;
int h[N][N];
int dist[N][N];
bool st[N][N];

struct Node
{
    int x, y, d;
    bool operator< (const Node& t) const    //小顶堆
    {
        return d > t.d;
    }
};

int main()
{
    int T;
    cin >> T;
    for (int C = 1; C <= T; ++C)
    {
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin >> h[i][j];
            }
        }
        memset(dist, 0x3f, sizeof dist);
        memset(st, 0, sizeof st);
        priority_queue<Node> heap;

        for (int i = 0; i < n; ++i)
        {
            heap.push({i, 0, h[i][0]});
            dist[i][0] = h[i][0];
            heap.push({i, m - 1, h[i][m - 1]});
            dist[i][m - 1] = h[i][m - 1];
        }
        for (int i = 1; i < m - 1; ++i)
        {
            heap.push({0, i, h[0][i]});
            dist[0][i] = h[0][i];
            heap.push({n - 1, i, h[n - 1][i]});
            dist[n - 1][i] = h[n - 1][i];
        }

        int ret = 0;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        while (heap.size())
        {
            Node t = heap.top();
            heap.pop();

            if (st[t.x][t.y])   continue;
            st[t.x][t.y] = true;
            ret += t.d - h[t.x][t.y];

            for (int i = 0; i < 4; ++i)
            {
                int x = t.x + dx[i], y = t.y + dy[i];
                if (x >= 0 && x < n && y >=0 && y < m)
                {
                    if (dist[x][y] > max(t.d, h[x][y]))
                    {
                        dist[x][y] = max(t.d, h[x][y]);
                        heap.push({x, y, dist[x][y]});
                    }
                }
            }
        }

        cout << "Case #" << C << ": " << ret << endl;
    }

    return 0;
}