✅ C++ || WITH & W/O VISITED MATRIX || PRIORITY QUEUE , BFS || CLEAN CODE WITH EXPLANATION
We can only store water in a block only if the depth(value) of a cell is less than the boundary otherwise the water will flow out . So we are keeping track of o
We can only store water in a block only if the depth(value) of a cell is less than the boundary otherwise the water will flow out . So we are keeping track of only boundary . We store the boundary in a min heap (priority queue) . We keep removing the smallest boundary element and check for it\'s neighbours where 3 cases can arise - 1. neighbour is already present in boundary (visited) , 2. neighbour is smaller , 3. neighbour >= boundary . In 1 case we don\'t have to do anything and move to other neighbours. In 2 case we can store water equal to boundary-neighbour , so we add that to ans and increase that neighbour to boundary and add that to boundary . In 3 case we can\'t store water , so we do nothing and add that element to boundary . We keep doing this till we have covered all elements of boundary .\n\n**1.  Using visited matrix**\n```\nint trapRainWater(vector<vector<int>>& a) {\n        int m,n,i,j;\n        m=a.size();\n        n=a[0].size();\n        int water=0;\n        \n        vector<vector<bool>> vis(m,vector<bool>(n,0));\n        priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> q;\n        \n        for(i=0;i<n;i++)\n        {\n            q.push({a[0][i],0,i});\n            q.push({a[m-1][i],m-1,i});\n            vis[0][i]=1;\n            vis[m-1][i]=1;\n        }\n        \n        for(i=0;i<m;i++)\n        {\n            q.push({a[i][0],i,0});\n            q.push({a[i][n-1],i,n-1});\n            vis[i][0]=1;\n            vis[i][n-1]=1;\n        }\n                    \n        while(!q.empty())\n        {\n            int x=q.top()[0];\n            i=q.top()[1];\n            j=q.top()[2];\n            q.pop();\n            \n            if(j-1>=0 && !vis[i][j-1])\n            {\n                if(a[i][j-1]<x)\n                {\n                    water+=(x-a[i][j-1]);\n                    a[i][j-1]=x;\n                }\n                \n                q.push({a[i][j-1],i,j-1});\n                vis[i][j-1]=1;\n            }   \n            \n            if(j+1<n && !vis[i][j+1])\n            {\n                if(a[i][j+1]<x)\n                {\n                    water+=(x-a[i][j+1]);\n                    a[i][j+1]=x;\n                }\n                \n                q.push({a[i][j+1],i,j+1});\n                vis[i][j+1]=1;\n            } \n            \n            if(i-1>=0 && !vis[i-1][j])\n            {\n                if(a[i-1][j]<x)\n                {\n                    water+=(x-a[i-1][j]);\n                    a[i-1][j]=x;\n                }\n                \n                q.push({a[i-1][j],i-1,j});\n                vis[i-1][j]=1;\n            }  \n            \n            if(i+1<m && !vis[i+1][j])\n            {\n                if(a[i+1][j]<x)\n                {\n                    water+=(x-a[i+1][j]);\n                    a[i+1][j]=x;\n                }\n                \n                q.push({a[i+1][j],i+1,j});\n                vis[i+1][j]=1;\n            }  \n        }\n        return water;\n    }\n```\n------------------------------------------------------------------------------\n**2.  Witout using visited matrix**\n```\nint trapRainWater(vector<vector<int>>& a) {\n        int m,n,i,j;\n        m=a.size();\n        n=a[0].size();\n        int water=0;\n        \n        priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> q;\n        \n        for(i=0;i<n;i++)\n        {\n            q.push({a[0][i],0,i});\n            q.push({a[m-1][i],m-1,i});\n            a[0][i]=-1;\n            a[m-1][i]=-1;\n        }\n        \n        for(i=0;i<m;i++)\n        {\n            q.push({a[i][0],i,0});\n            q.push({a[i][n-1],i,n-1});\n            a[i][0]=-1;\n            a[i][n-1]=-1;\n        }\n                    \n        while(!q.empty())\n        {\n            int x=q.top()[0];\n            i=q.top()[1];\n            j=q.top()[2];\n            q.pop();\n            \n            if(j-1>=0 && a[i][j-1]!=-1)\n            {\n                if(a[i][j-1]<x)\n                {\n                    water+=(x-a[i][j-1]);\n                    a[i][j-1]=x;\n                }\n                \n                q.push({a[i][j-1],i,j-1});\n                a[i][j-1]=-1;\n            }   \n            \n            if(j+1<n && a[i][j+1]!=-1)\n            {\n                if(a[i][j+1]<x)\n                {\n                    water+=(x-a[i][j+1]);\n                    a[i][j+1]=x;\n                }\n                \n                q.push({a[i][j+1],i,j+1});\n                a[i][j+1]=-1;\n            } \n            \n            if(i-1>=0 && a[i-1][j]!=-1)\n            {\n                if(a[i-1][j]<x)\n                {\n                    water+=(x-a[i-1][j]);\n                    a[i-1][j]=x;\n                }\n                \n                q.push({a[i-1][j],i-1,j});\n                a[i-1][j]=-1;\n            }  \n            \n            if(i+1<m && a[i+1][j]!=-1)\n            {\n                if(a[i+1][j]<x)\n                {\n                    water+=(x-a[i+1][j]);\n                    a[i+1][j]=x;\n                }\n                \n                q.push({a[i+1][j],i+1,j});\n                a[i+1][j]=-1;\n            }  \n        }\n        return water;\n    }\n```\n\n**Do share your suggestions & upvote if you like !!** \uD83D\uDE0A
['Breadth-First Search', 'C', 'Heap (Priority Queue)', 'C++']