CPP DFS solution explained
I recently got this in an assessment. \n\nget clusters in every step. \n\ndeal with the largest clusters and expand all the other clusters.\n\nlets take the sam
I recently got this in an assessment. \n\nget clusters in every step. \n![image](https://assets.leetcode.com/users/images/2fba1bf5-a2e6-4a08-9f3b-1c204d76a2ac_1600154624.5271661.png)\ndeal with the largest clusters and expand all the other clusters.\n\nlets take the sample case\n![image](https://assets.leetcode.com/users/images/9bfa313a-66b8-48ce-9cea-5bd596982525_1600155241.5790663.png)\n![image](https://assets.leetcode.com/users/images/7d0a1b56-35c6-4a4f-aa12-274beca688c4_1600155666.2390857.png)\n\n\n\n```\nclass cluster\n{\n    public:\n        set<pair<int,int>> c; // set of cells that are contaminated\n        set<pair<int,int>> uc; // set of cells that are next to this cluster and are uncontaminated\n        int wcnt = 0;       // walls required to contain this structure \n    \n};\nclass Solution {\npublic:\n    \n    void dfs(vector<vector<int>> &grid, int i, int j, vector<vector<bool>> &vis, cluster &cl)\n    {\n        if(i == grid.size() || i < 0 || j < 0 || j == grid[0].size()||vis[i][j]||grid[i][j] == -1)\n        {\n            // if the current src is out of grid bounds or if the cell is already visited  or current cell is already walled that is -1\n            return;\n        }\n        if(grid[i][j] == 0)\n        {\n            // if cell is uncontaminated then add to the uncontaminatd cells (uc) and increment wall cnt \n            cl.wcnt++;\n            cl.uc.insert({i,j});\n            return;\n        }\n        // if current cell is contaminated add to contaminated and mark vis = true\n        cl.c.insert({i,j});\n        vis[i][j] = true;\n        // call dfs in all directions\n        dfs(grid,i+1,j,vis,cl); // above\n        dfs(grid,i-1,j,vis,cl); // below\n        dfs(grid,i,j+1,vis,cl); // right\n        dfs(grid,i,j-1,vis,cl); // left\n        \n    }\n\n    int containVirus(vector<vector<int>>& grid) {\n    \n        // row ka size\n        int n = grid.size();\n        // col ka size\n        int m = grid[0].size();\n        int ans = 0;\n        while(1)\n        {\n            // visisted matrix\n            vector<vector<bool>> vis(n,vector<bool>(m));\n            // comparator for pq to sort it according to size of uncontaminated cells in cluster\n            auto comp=[](const cluster& A,const cluster& B)\n            { \n                return A.uc.size()<B.uc.size();\n            };\n            // initialise priority queue\n            priority_queue<cluster,vector<cluster>, decltype(comp)> pq(comp);\n            // search for a contaminated cell in the grid\n            for(int i = 0; i<n; i++)\n            {\n                for(int j = 0; j<m; j++)\n                {\n                    if(!vis[i][j]&&grid[i][j] == 1)\n                    {\n                        // create a cluster\n                        cluster c;\n                        // call dfs\n                        dfs(grid,i,j,vis,c);\n                        pq.push(c);\n\n                    }\n                }\n            }\n            // if size of priority queue is 0 the termination condition is reached ie all contaminated cells are contained.\n            if(pq.size()==0)\n            break;\n            // get the biggest cluster is found make em all -1 and add the walls reqd to contain them \n            cluster k = pq.top();\n            pq.pop();\n            for(auto x: k.c)\n            {\n                grid[x.first][x.second] = -1;\n            }\n            ans += k.wcnt;\n\n            // for the rest of the clusters make their uncontaminated cells as contaminated\n            while(!pq.empty())\n            {\n                cluster k1 = pq.top();\n                pq.pop();\n                for(auto x: k1.uc)\n                {\n                    grid[x.first][x.second] = 1;\n                }   \n            }\n         \n        }\n        \n        return ans;\n    }\n};\n\n```
['Depth-First Search', 'C++']