C++ Prority Queue + BFS
\n// TC -> O(N * M * log NM)\n// SC -> O(N * M)\n\nclass Cell {\npublic:\n    int r;\n    int c;\n    int h;\n    Cell(int r, int c, int h) {\n        this->r =
```\n// TC -> O(N * M * log NM)\n// SC -> O(N * M)\n\nclass Cell {\npublic:\n    int r;\n    int c;\n    int h;\n    Cell(int r, int c, int h) {\n        this->r = r;\n        this->c = c;\n        this->h = h;\n    }\n    \n    bool operator<(const Cell& cell) const {\n        return (this->h < cell.h);\n    }\n    \n    bool operator>(const Cell& cell) const {\n        return (this->h > cell.h);\n    }\n    \n    void Print() {\n        cout<<"r:"<<r<<"\\tc:"<<c<<"\\th:"<<h<<endl;\n    }\n};\n\nclass Solution {\nprivate:\n    int dirs[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };\npublic:\n    int trapRainWater(vector<vector<int>>& heightMap) {\n        if (heightMap.size() == 0 || heightMap[0].size() == 0) {\n            return 0;\n        }\n        \n        int maxRow = heightMap.size();\n        int maxCol = heightMap[0].size();\n        // minHeap to hold all cells\n        priority_queue<Cell, vector<Cell>, greater<Cell>> pq;\n        // Boolean matrix to mark visited\n        vector<vector<bool>> visited(maxRow, vector<bool>(maxCol, false));\n        int maxWater = 0;\n        \n        \n        // Add all the edge cells to the pq as they cannot hold any water and mark them visited as well\n        \n        // Add first and last row\n        for (int col = 0; col < maxCol; col++) {\n            visited[0][col] = true;\n            visited[maxRow - 1][col] = true;\n            pq.push(Cell(0, col, heightMap[0][col]));\n            pq.push(Cell(maxRow - 1, col, heightMap[maxRow -1][col]));\n        }\n        \n        // Add first col and last col\n        for (int row = 0; row < maxRow; row++) {\n            visited[row][0] = true;\n            visited[row][maxCol - 1] = true;\n            pq.push(Cell(row, 0, heightMap[row][0]));\n            pq.push(Cell(row, maxCol - 1, heightMap[row][maxCol - 1]));\n        }\n        \n        // Iterate over the pq and add traverse/visit each cell\'s neighbor if not already visited\n        while (!pq.empty()) {\n            Cell cell = pq.top();\n            pq.pop();\n            \n            //cell.Print();\n            \n            // Traverse all four neighbors\n            for (auto dir: dirs) {\n                int row = cell.r + dir[0];\n                int col = cell.c + dir[1];\n                \n                if (row > 0 && row < maxRow - 1 && col > 0 && col < maxCol - 1 && !visited[row][col]) {\n                    // Mark the neighbor visited\n                    visited[row][col] = true;\n                    \n                    maxWater += max(0, cell.h - heightMap[row][col]);\n                    pq.push(Cell(row, col, max(cell.h, heightMap[row][col])));\n                }\n            }\n            \n        }\n        \n        return maxWater;\n    }\n};\n```
['Breadth-First Search', 'C', 'Heap (Priority Queue)']