BFS Solution ✅✅
Approach
Use a priority queue to store boundary cells, starting with the smallest height. Each entry in the queue is of the form {height, {row, col}}.
Mark boun
# Approach
<!-- Describe your approach to solving the problem. -->
1. Use a priority queue to store boundary cells, starting with the smallest height. Each entry in the queue is of the form `{height, {row, col}}`.
2. Mark boundary cells as visited to avoid revisiting them.
3. Process cells using BFS:
    - For each cell popped from the queue, explore its four neighbors.
    - If a neighbor is unvisited, calculate how much water it can trap `(max(0, current_height - neighbor_height))`.
    - Add the neighbor to the queue with its updated height `(max(current_height, neighbor_height))`.
4. Continue until all reachable cells are processed.

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

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

# Code
```cpp []
class Solution {
public:

    int trapRainWater(vector<vector<int>>& height) {
        int n = height.size();
        int m = height[0].size();

        // pair<int, pair<int, int>> 
        //{height, {r, c}}
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;

        vector<vector<int>> vis(n, vector<int>(m));

        //first and last column
        for(int i=0; i<n; i++){
            vis[i][0] = 1;
            vis[i][m-1] = 1;
            pq.push({height[i][0], {i, 0}});
            pq.push({height[i][m-1], {i, m-1}});
        }
        //first and last row
        for(int i=0; i<m; i++){
            vis[0][i]=1;
            vis[n-1][i]=1;
            pq.push({height[0][i], {0, i}});
            pq.push({height[n-1][i], {n-1, i}});
        }
        int ans=0;
        while(!pq.empty()){
            int h = pq.top().first;
            int r = pq.top().second.first;
            int c = pq.top().second.second;
            pq.pop();

            int dr[] = {-1, 0, 1, 0};
            int dc[] = {0, -1, 0, 1};
            for(int i=0; i<4; i++){
                int nr = r + dr[i];
                int nc = c + dc[i];
                if(nr>=0 && nr<n && nc>=0 && nc<m && !vis[nr][nc]){
                    ans+=max(0, h-height[nr][nc]);
                    pq.push({max(h, height[nr][nc]), {nr, nc}});
                    vis[nr][nc] = 1;
                }
            }
        }
        return ans;
    }
};
```
```Python []
import heapq

class Solution:
    def trapRainWater(self, height):
        n = len(height)
        m = len(height[0])

        pq = []  # Min-heap
        vis = [[False] * m for _ in range(n)]

        # Add first and last column
        for i in range(n):
            vis[i][0] = True
            vis[i][m - 1] = True
            heapq.heappush(pq, (height[i][0], i, 0))
            heapq.heappush(pq, (height[i][m - 1], i, m - 1))

        # Add first and last row
        for i in range(m):
            vis[0][i] = True
            vis[n - 1][i] = True
            heapq.heappush(pq, (height[0][i], 0, i))
            heapq.heappush(pq, (height[n - 1][i], n - 1, i))

        ans = 0
        dr = [-1, 0, 1, 0]
        dc = [0, -1, 0, 1]

        while pq:
            h, r, c = heapq.heappop(pq)

            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]

                if 0 <= nr < n and 0 <= nc < m and not vis[nr][nc]:
                    ans += max(0, h - height[nr][nc])
                    heapq.heappush(pq, (max(h, height[nr][nc]), nr, nc))
                    vis[nr][nc] = True

        return ans

```
```Java []
import java.util.PriorityQueue;

class Solution {
    public int trapRainWater(int[][] height) {
        int n = height.length;
        int m = height[0].length;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[][] vis = new boolean[n][m];

        // Add first and last column
        for (int i = 0; i < n; i++) {
            vis[i][0] = true;
            vis[i][m - 1] = true;
            pq.offer(new int[]{height[i][0], i, 0});
            pq.offer(new int[]{height[i][m - 1], i, m - 1});
        }

        // Add first and last row
        for (int i = 0; i < m; i++) {
            vis[0][i] = true;
            vis[n - 1][i] = true;
            pq.offer(new int[]{height[0][i], 0, i});
            pq.offer(new int[]{height[n - 1][i], n - 1, i});
        }

        int ans = 0;
        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, -1, 0, 1};

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int h = curr[0], r = curr[1], c = curr[2];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m && !vis[nr][nc]) {
                    ans += Math.max(0, h - height[nr][nc]);
                    pq.offer(new int[]{Math.max(h, height[nr][nc]), nr, nc});
                    vis[nr][nc] = true;
                }
            }
        }

        return ans;
    }
}

```
['Breadth-First Search', 'Python', 'C++', 'Java']