C++ || BFS + Priority Queue || Easy Explanation || Asked in Google
Imagine a water pool which is build with colums of different height, the level of water will be equal to height of lowest column and the excess water will be ou
Imagine a water pool which is build with colums of different height, the level of water will be equal to height of lowest column and the excess water will be out from the lowest column. \nWe need to check the surrounding columns/cells this gives us idea of BFS and because of above condition we get intution of **BFS with Priority Queue**.\nPriority Queue will keep track of cell positioned at [i,j] with height h and will maintain the increasing order of heights of cells.\n\nLets take a example:\n\n**Step 0:**\n\n```\n3 3 3 3\n3 0 1 2\n3 3 3 3\n```\n\nHere we can see that the outer cells can\'t contain water and the BFS would start from OuterWards to inner side. In first step 2 with all 3 of outer side would be pushed priority queue.\n\n**Step 1:**\n********\n```\n3 3 3 3\n3 0 2 2\n3 3 3 3\n```\n\ntotal water after 1 step would be : water += 2(min height of all visited neighbour) - 1(curr height of Cell)  ; //**water =0 + 1 = 1;**\n\n*How 2 came* : 2 = min(3,2,3) // why we didn\'t chose 0 because it was not visited\n\n**Step 2 :**\n\n```\n3 3 3 3\n3 2 2 2\n3 3 3 3\n```\n\ntotal water after step 2 would be : water += 2(min height of all visited neighbour) - 0(curr height of cell); **water = 1 + 2 = 3;**\n\n*how 2 came* : 2 =  min(3,2,3,3);\n\nLets Move to code To get Clear Idea :\n\n```\nclass Solution {\npublic:\n\tbool vis[201][201];                                                           //to keep track of visited cell\n    int n,m;\n    bool isValid(int i, int j){\n        if(i<0 || i>=m || j<0 || j>=n || vis[i][j]==true)  return false;\n        \n        return true;\n    }\n    int trapRainWater(vector<vector<int>>& heightMap) {\n        vector<vector<int>> dir {{1,0},{-1,0},{0,1},{0,-1}};          //direction Vector\n        m = heightMap.size();   if(m==0)    return 0;                // m=0 is one edge case\n        n = heightMap[0].size();\n        memset(vis,false,sizeof(vis));\n        priority_queue<pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>> , greater<pair<int,pair<int,int>>> >pq;                                // min heap w.r.t cell height\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                if(i==0 || j==0 || i==m-1 || j==n-1){\n                    pq.push({heightMap[i][j],{i,j}});                          //pushing all outer cells in pq\n                    vis[i][j]=true;\n                }   \n            }\n        }\n        int water = 0;\n        int Height = INT_MIN;\n        while(!pq.empty()){                                                       //normal BFS\n            auto pr =  pq.top();\n            pq.pop();\n            int height = pr.first;\n            int i = pr.second.first;\n            int j = pr.second.second;\n            Height = max(Height,height);\n            for(int d=0;d<4;d++){                                            //iterating through direction vector\n                int x = i + dir[d][0];\n                int y = j + dir[d][1];\n                if(isValid(x,y)){\n                   water += max(0, Height - heightMap[x][y]);      //just adding the diff between cell height and surrounding height\n                   vis[x][y]=true;\n                   pq.push({heightMap[x][y],{x,y}});\n                }\n            }            \n        }\n        return water;\n\t\t}\n\t};\n```
['Breadth-First Search', 'C', 'Heap (Priority Queue)']