C++ solution using recursion (beats 99.37%)


  • 0
    V

    The general idea is to keep the boundary cells in a min heap, then find the first cells (using recursion) that are higher than the cell on the top of the heap, and push those cells to the heap which form the new boundary.

    struct Node {
        Node(int r, int c, int h):row(r),col(c),height(h) {}
        int row;
        int col;
        int height;
        bool operator<(const Node& n1) const {
            return height > n1.height;
        }
    };
    
    class Solution {
    public:
        priority_queue<Node> q;
        vector<vector<bool> > visited;
        int volumn;
        int numberVisited;
        Solution() {
            volumn = 0;
            numberVisited = 0;
        }
        void checkNeighbor(int r, int c, vector<vector<int> >& heights, int& baseHeight) {
            visited[r][c] = true;
            numberVisited += 1;
            if (heights[r][c] >= baseHeight) {
                Node newBoundary(r, c, heights[r][c]);
                q.push(newBoundary);
                return;
            } else {
                volumn += baseHeight - heights[r][c];
                if (r-1 >= 0 && !visited[r-1][c]) checkNeighbor(r-1, c, heights, baseHeight);//up
                if (c+1 < visited[0].size() && !visited[r][c+1]) checkNeighbor(r, c+1, heights, baseHeight);//right
                if (r+1 < visited.size() &&!visited[r+1][c]) checkNeighbor(r+1, c, heights, baseHeight);//down
                if (c-1 >= 0 && !visited[r][c-1]) checkNeighbor(r, c-1, heights, baseHeight);//left
            }
        }
    
        int trapRainWater(vector<vector<int>>& heights) {
            if (heights.size() == 0) return 0;
            int r = heights.size();
            int c = heights[0].size();
            int total = r*c;
            for (int i = 0; i < r; i++) {
                vector<bool> oneRow(c, false);
                visited.push_back(oneRow);
            }
            //initialize boundary
            //row 0, row r-1
            for (int i = 0; i < c; i++) {
                Node nodeTop(0, i, heights[0][i]);
                Node nodeBottom(r-1, i, heights[r-1][i]);
                q.push(nodeTop);
                q.push(nodeBottom);
                visited[0][i] = true;
                visited[r-1][i] = true;
                numberVisited += 2;
            }
            //col 0, col c-1
            for (int i = 1; i < r-1; i++) {
                Node nodeL(i, 0, heights[i][0]);
                Node nodeR(i, c-1, heights[i][c-1]);
                q.push(nodeL);
                q.push(nodeR);
                visited[i][0] = true;
                visited[i][c-1] = true;
                numberVisited += 2;
            }
            while (numberVisited < total) {
                Node base = q.top();
                q.pop();
                int r0 = base.row;
                int c0 = base.col;
                //check neighbors
                if (r0-1 >= 0 && !visited[r0-1][c0]) checkNeighbor(r0-1, c0, heights, base.height);//up
                if (c0+1 < c && !visited[r0][c0+1]) checkNeighbor(r0, c0+1, heights, base.height);//right
                if (r0+1 < r &&!visited[r0+1][c0]) checkNeighbor(r0+1, c0, heights, base.height);//down
                if (c0-1 >= 0 && !visited[r0][c0-1]) checkNeighbor(r0, c0-1, heights, base.height);//left
            }
            return volumn;
    
        }
    };```

Log in to reply
 

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