C++ solution using recursion (beats 99.37%)

• 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;

}
};`````````

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