leetcode 接雨水二

class POINT{            //定义point类，将坐标x、y、高度封装到同一class中
public:
    int _x;
    int _y;
    int _height;
    POINT(int x ,int y ,int h) : _x(x),_y(y),_height(h){}   //构造函数
    bool operator <(const POINT& a) const {                 //重载比较函数配合优先级队列
        return _height > a._height;
    }
  // bool operator ()( node a, node b){  这个运行不了 需要对比较函数进行重构
    //    return a._height >b._height;
  //}
};
//正常情况下，priority_queue采用的是从队尾弹出元素，也就是如果重载函数要求从小到大排序  
//那么会弹出最大的那个元素，重构比较函数之后，则弹出最小的元素
class Solution {
public:

int trapRainWater(vector<vector<int>>& maps){
    int ret = 0;
    int row = maps.size();
    int col = maps[0].size();
    if(row<3 || col <3)     return ret;             //去除存不住水的情况，直接返回0

    priority_queue<POINT> que;                      //优先级队列，用于获取当前最短板
    vector<vector<bool>> visited(row,vector<bool>(col,false));//用来标记该点已被更小的圈囊括
   
    // //把最外围一圈先加入优先级队列
    for(int i = 0;i<col;++i)                        //把最外围一圈先加入优先级队列
    {
        que.push(POINT(0,i,maps[0][i]));
        visited[0][i] = true;
        que.push(POINT(row-1,i,maps[row-1][i]));
        visited[row-1][i] = true;
    }
    for(int i = 1;i<row-1;++i)
    {
        que.push(POINT(i,0,maps[i][0]));
        visited[i][0] = true;
        que.push(POINT(i,col-1,maps[i][col-1]));
        visited[i][col-1] = true;
    }

    
    int nowLowH = 0;                //此变量记录当前的短板高度

    while(que.size())
    {
        auto temp = que.top();      //取出当前最短板的point
        int nowX = temp._x;
        int nowY = temp._y;
        int nowH = temp._height;
        que.pop();

        nowLowH = max(nowLowH,nowH);//确定此时的最短板高度

        if(nowX>0 && !visited[nowX-1][nowY])        //四个方向进行扩散
        {
            if(maps[nowX-1][nowY] < nowLowH)      //此点没有当前短板高，即其可以蓄水到当前短板高度
            {
                ret += (nowLowH - maps[nowX-1][nowY]);        
            }  
            visited[nowX-1][nowY] = true;         //标记为已访问，加入队列
            que.push(POINT(nowX-1,nowY,maps[nowX-1][nowY]));     
        }

        if(nowX<row-1 && !visited[nowX+1][nowY])
        {
            if(maps[nowX+1][nowY] < nowLowH)
            {
                ret += (nowLowH - maps[nowX+1][nowY]);
            }        
            visited[nowX+1][nowY] = true;
            que.push(POINT(nowX+1,nowY,maps[nowX+1][nowY]));
        }

        if(nowY>0 && !visited[nowX][nowY-1])
        {
            if(maps[nowX][nowY-1] < nowLowH)
            {
                ret += (nowLowH - maps[nowX][nowY-1]);        
            }  
            visited[nowX][nowY-1] = true; 
            que.push(POINT(nowX,nowY-1,maps[nowX][nowY-1]));     
        }

        if(nowY<col-1 && !visited[nowX][nowY+1])
        {
            if(maps[nowX][nowY+1] < nowLowH)
            {
                ret += (nowLowH - maps[nowX][nowY+1]);
            }        
            visited[nowX][nowY+1] = true;
            que.push(POINT(nowX,nowY+1,maps[nowX][nowY+1]));
        }

    }

    return ret;
    }
};

//priority_queue引用比较示例
//class cmp{
//public:
  //  bool operator()(vector<int>&a,vector<int>&b){
    //    return a[0]>b[0]; 
    //}
//};
//priority_queue<vector<int>,vector<vector<int>>,cmp> q;//小顶堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110