Short Board Effect - BFS over min heap (Beats 97%)
IntuitionApproachWhich cell's water intake can be determined at the beginning?
The outermost cells can't receive water.
Assuming that the height of (0,1) is the
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
![board.png](https://assets.leetcode.com/users/images/e8e7689f-86a6-4a73-a1b9-f19510e3a7f4_1737258256.0273747.png)


# Approach
<!-- Describe your approach to solving the problem. -->
**Which cell's water intake can be determined at the beginning?**

- The outermost cells can't receive water.
- Assuming that the height of (0,1) is the smallest in the outermost cells and the height is equal to 5, then (1,1) adjacent to it, we know:
  - The water level of (1,1) cannot exceed 5, otherwise water will flow out of (0,1).
  - The max water level of (1,1) is 5, because the height of (0,1) is the smallest in the outermost cells, and the water of (1,1) cannot flow out from other places.

Let's start with the outermost grid. Imagine a wooden barrel, and the height of the outermost cells is regarded as the height of the board.

Then we continue the above discussion:

- If the height of (1,1) is more than or equal to 5, then (0,1) is useless. Let's remove (0,1) and use (1,1) instead.
- If the height of (1,1) is less than 5, then we can fill it with water height of 5. Then let's assume the height of 5 is board instead of water. Then, if the height of (1,1) is filled to 5, the board (0,1) can still be removed and replaced with the board (1,1) with a height of 5.

**Because we have to find the shortest board every time, we maintain the height of the board with a min heap. According to the above practice, keep looping until the min heap is empty.**

# Code
```cpp []
class Solution {
   public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();
        if (m <= 2 || n <= 2) return 0;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        vector<vector<bool>> visited(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) {
                    pq.emplace(heightMap[i][j], i, j);
                    visited[i][j] = true;
                }
            }
        }
        int volume = 0;
        while (!pq.empty()) {
            auto [height, i, j] = pq.top();
            pq.pop();
            for (auto& [di, dj] : DIRS) {
                int ni = i + di, nj = j + dj;
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                    volume += max(height - heightMap[ni][nj], 0);
                    pq.emplace(max(height, heightMap[ni][nj]), ni, nj);
                    visited[ni][nj] = true;
                }
            }
        }
        return volume;
    }

   private:
    static constexpr int DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
};
```

# Complexity
- Time complexity: $$O(mnlog(mn))$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(mn)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->


['Breadth-First Search', 'Heap (Priority Queue)', 'C++']