C++ Floodfill solution with priority_queue


  • 2
    Y
    class Solution {
    public:
        int trapRainWater(vector<vector<int>>& heightMap) {
            int n = heightMap.size();
            if(n == 0) return 0;
            int m = heightMap[0].size();
            if(m == 0) return 0;
            int result = 0;
            vector<vector<bool>> isVisit(n, vector<bool>(m, false));
            priority_queue<pair<int, pair<int, int>>> myQueue;
            
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(i==0 || i == n-1 || j == 0 || j == m-1) {
                        // we push all the boundary points into the priorrity_queue
                        isVisit[i][j] = true;
                        // push negative height as the priority_queue is a big heap
                        myQueue.push(make_pair(-heightMap[i][j], make_pair(i, j)));
                    }
                }
            }
            const int go_x[4] = {1, -1, 0, 0};
            const int go_y[4] = {0, 0, 1, -1};
            while(!myQueue.empty()) {
                // We always extract the smallest block and try to extend it to its four neighbors.
                auto temp_front = myQueue.top();
                myQueue.pop();
                int temp_height = -temp_front.first;
                int fx = temp_front.second.first;
                int fy = temp_front.second.second;
                for(int d = 0; d < 4; d++) {
                    int tx = fx + go_x[d];
                    int ty = fy + go_y[d];
                    if(tx < 0 || tx >=n || ty < 0 || ty >= m || isVisit[tx][ty]) continue;
                    if(heightMap[tx][ty] < temp_height) {
                        // if its neightbour's height is smallest than it, we fill water in it.
                        result += (temp_height - heightMap[tx][ty]);
                        heightMap[tx][ty] = temp_height;
                    }
                    isVisit[tx][ty] = true;
                    myQueue.push(make_pair(-heightMap[tx][ty], make_pair(tx, ty)));
                }
            }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.