ONLY GOD KNOWS
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int bfs(int r,int c,vector<vector<int>>& isInfected,vector<vector<bool>>& vis,vector<vector<bool>>& cont){\n        int count=0;\n        int row=isInfected.size();\n        int col=isInfected[0].size(); \n\n        queue<pair<int,int>> q;\n        q.push({r,c});      \n        vis[r][c]=true;\n\n        int dx[4]={0,-1,0,1};\n        int dy[4]={1,0,-1,0};\n\n        vector<vector<bool>> seen(row,vector<bool>(col,false)); \n\n        while(!q.empty()){\n\n             int u=q.front().first;\n             int v=q.front().second;\n             q.pop();\n\n             for(int k=0;k<4;++k){\n                int nr=u+dx[k];\n                int nc=v+dy[k];\n\n                if(0<=nr && nr<row && 0<=nc && nc<col && !vis[nr][nc] && !cont[nr][nc]){\n                   if(isInfected[nr][nc]){\n                      vis[nr][nc]=true;\n                      q.push({nr,nc});   \n                   }\n                   else if(!isInfected[nr][nc]){\n                      if(!seen[nr][nc]){\n                         seen[nr][nc]=true;\n                         count++;  \n                      } \n                   }        \n                }   \n             }       \n        }\n\n        return count; \n    }  \n\n    int quarantine(int r,int c,vector<vector<int>>& isInfected,vector<vector<bool>>& cont){\n        \n        int row=isInfected.size();\n        int col=isInfected[0].size();\n\n        int dx[4]={0,-1,0,1};\n        int dy[4]={1,0,-1,0};\n\n        int walls=0;\n\n        queue<pair<int,int>> q;\n\n        vector<vector<bool>> vis(row,vector<bool>(col,false));\n\n        vis[r][c]=true; \n        cont[r][c]=true;\n        q.push({r,c});\n  \n        while(!q.empty()){\n\n             int u=q.front().first;\n             int v=q.front().second; \n             q.pop();\n\n             for(int k=0;k<4;++k){\n                 int nr=u+dx[k];\n                 int nc=v+dy[k];\n\n                 if(0<=nr && nr<row && 0<=nc && nc<col){\n                    if(!vis[nr][nc] && isInfected[nr][nc] && !cont[nr][nc]){\n                       vis[nr][nc]=true;\n                       cont[nr][nc]=true;\n                       q.push({nr,nc}); \n                    } \n                    else if(!isInfected[nr][nc])\n                       walls++;\n                 }     \n             }\n        }\n        //std::cout<<"Returning"<<std::endl;\n        return walls;         \n    } \n\n   void spread(int r,int c,vector<vector<int>>& isInfected,vector<vector<bool>>& seen,vector<vector<bool>>& mark,vector<vector<bool>>& cont){\n         \n        int row=isInfected.size();\n        int col=isInfected[0].size();\n        \n        int dx[4]={0,-1,0,1};\n        int dy[4]={1,0,-1,0};\n\n        queue<pair<int,int>> q;\n\n        q.push({r,c});\n        seen[r][c]=true;\n\n        while(!q.empty()){\n\n             int u=q.front().first;\n             int v=q.front().second;\n\n             q.pop();\n\n             for(int k=0;k<4;++k){\n\n                 int nr=u+dx[k];\n                 int nc=v+dy[k];\n\n                 if(0<=nr && nr<row && 0<=nc && nc<col){\n                    if(!seen[nr][nc] && isInfected[nr][nc] && !cont[nr][nc] && !mark[nr][nc]){\n                       seen[nr][nc]=true;\n                       q.push({nr,nc});\n                    } \n                    else if(!isInfected[nr][nc]){\n                       isInfected[nr][nc]=1;\n                       mark[nr][nc]=true;  \n                    }  \n                 }   \n             }  \n        }   \n\n        std::cout<<"No control here"<<std::endl;     \n   } \n\n    int containVirus(vector<vector<int>>& isInfected) {\n        int row=isInfected.size();\n        int col=isInfected[0].size();\n\n        int walls=0;\n        vector<vector<bool>> cont(row,vector<bool>(col,false));\n\n        while(true){\n\n             vector<vector<bool>> vis(row,vector<bool>(col,false));\n         \n             int maxm=0;\n             int maxr;\n             int maxc;\n\n             for(int i=0;i<row;++i){\n                 for(int j=0;j<col;++j){\n                     if(isInfected[i][j] && !vis[i][j] && !cont[i][j]){\n                        int infect=bfs(i,j,isInfected,vis,cont);\n\n                        //std::cout<<"Infected="<<infect<<std::endl;\n                        \n                        if(maxm<infect){\n                           maxm=infect;\n                           maxr=i;\n                           maxc=j;  \n                        }         \n                     }   \n                 }  \n             }\n\n             std::cout<<"First Iteration completed"<<std::endl;\n\n             std::cout<<"Maximum Infected="<<maxm<<std::endl;\n             if(maxm==0)\n                break;\n\n             walls+=quarantine(maxr,maxc,isInfected,cont);\n\n             std::cout<<"Walls required="<<walls<<std::endl;\n             \n             vector<vector<bool>> seen(row,vector<bool>(col,false));\n             vector<vector<bool>> mark(row,vector<bool>(col,false));\n\n             for(int i=0;i<row;++i){\n                 for(int j=0;j<col;++j){\n                     if(isInfected[i][j] && !seen[i][j] && !cont[i][j] && !mark[i][j])\n                        spread(i,j,isInfected,seen,mark,cont);  \n                 }  \n             }      \n\n             std::cout<<"Spread Done"<<std::endl;            \n        }\n        return walls;\n    }\n};\n```
['C++']