欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++ 的接雨水问题及题解分析

程序员文章站 2022-08-04 13:15:12
题目 给定一个m x n的矩阵,其中的值均为正整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。 说明: m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于...

题目

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

说明:

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

示例:

C++ 的接雨水问题及题解分析

如上图所示,这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。

C++ 的接雨水问题及题解分析

C++ 的接雨水问题及题解分析

下雨后,雨水将会被存储在这些方块中。总的接雨水量是4。

代码

struct node{
    int i,j,h;
    node(int ii,int jj,int hh):i(ii),j(jj),h(hh){}
    bool operator <(const node &root) const{
        return h>root.h;
    }
};

class solution {
public:
    int traprainwater(vector<vector<int>>& heightmap) {
        if(heightmap.size()==0) return 0;
        int m=heightmap.size(),n=heightmap[0].size(),area=0,h=0;
        priority_queue<node,vector<node>> q;
        vector<vector<bool>> visit(m,vector<bool>(n,false));
        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(node(i,j,heightmap[i][j]));
                    visit[i][j]=true;
                }
            }
        }
        vector<int> x={0,0,-1,1},y={-1,1,0,0};
        while(!q.empty()){
            auto f=q.top();
            if(h<f.h) h++;
            else{
                q.pop();
                for(int k=0;k<4;k++){
                    int i=f.i+x[k],j=f.j+y[k];
                    if(i>=0&&i<m&&j>=0&&j<n&&visit[i][j]==false){
                        int hh=heightmap[i][j];
                        if(hh<h) area+=h-hh;
                        q.push(node(i,j,hh));
                        visit[i][j]=true;
                    }
                }
            }
        }
        return area;
    }
};