Priority Queue and BFS!
Here the main idea is to traverse the boundary elements and store them in a priority queue and then marking them in the visited array. Then we follow the standa
Here the main idea is to traverse the boundary elements and store them in a priority queue and then marking them in the visited array. Then we follow the standard BFS algo and traverse towards the center of the grid.\nIf the lvel of water in the adj position is lesser, we can strore water in it and deligate the responsiblilty. If it is more or of equal level, we can\'t store water but can transfer the responsibility to that. \nWe store the level of water in a "res" integer and return it in the last.\n\n```\nclass Solution {\npublic:\n    int trapRainWater(vector<vector<int>>& grid) {\n        int row=grid.size();\n        int col=grid[0].size();\n        \n        //pair<int,pair<int,int>>     height, row, col\n        priority_queue <pair<int,pair<int,int>>, \n        vector<pair<int,pair<int,int>>>, \n        greater<pair<int,pair<int,int>>>> pq;\n        \n        vector<vector<int>> vis(row,vector<int>(col,0));\n        for(int i=0;i<col;i++){\n            vis[0][i]=1; vis[row-1][i]=1;\n            pq.push({grid[0][i],{0,i}});\n            pq.push({grid[row-1][i],{row-1,i}});\n        }\n        for(int i=0;i<row;i++){\n            vis[i][0]=1; vis[i][col-1]=1;\n            pq.push({grid[i][0],{i,0}});\n            pq.push({grid[i][col-1],{i,col-1}});\n        }\n        // for(int i=0;i<row;i++){\n        //     for(int j=0;j<col;j++){\n        //         cout<<vis[i][j]<<" ";\n        //     }\n        //     cout<<endl;\n        // }\n        \n        int res=0;\n        while(!pq.empty()){\n            auto it= pq.top();\n            pq.pop();\n            int height=it.first;\n            int x=it.second.first;\n            int y=it.second.second;\n            \n            int dx[]={1,0,-1,0};\n            int dy[]={0,1,0,-1};\n            \n            for(int k=0;k<4;k++){\n                int newx=x+dx[k];\n                int newy=y+dy[k];\n                if(newx>0 && newx<row && newy>0 && newy<col){\n                    if(vis[newx][newy]==0){ //not visited\n                        if(grid[newx][newy]>height){\n                            pq.push({grid[newx][newy],{newx,newy}});\n                            vis[newx][newy]=1;\n                        }\n                        else if(grid[newx][newy]==height){\n                            pq.push({grid[newx][newy],{newx,newy}});\n                            vis[newx][newy]=1;\n                        }\n                        else if(grid[newx][newy]<height){\n                            res=res+(height-grid[newx][newy]);\n                            pq.push({height,{newx,newy}});\n                            vis[newx][newy]=1;\n                        }\n                    }\n                }\n            }\n        }\n        return res;\n    }\n};\n```
['Breadth-First Search', 'C', 'Heap (Priority Queue)']