Simple DFS based component counting + Implementation skills
Intuition\nSimple DFS based component counting + Implementation skills.\n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\nSimple DFS based component counting + Implementation skills.\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```\nusing pii=pair<int,int>;\n\n#define F first\n#define S second\n\nint dx[]={1,-1,0,0};\nint dy[]={0,0,1,-1};\n\nclass Solution {\nprivate:\nvoid print_grid(vector<vector<int>>& grid) {\n    int m=grid.size(),n=grid[0].size();\n    for (int i=0;i<m;i++) { for(int j=0;j<n;j++) {\n        cout<<(grid[i][j]?"O":".");\n    } cout<<endl; }\n}\n\nbool simulate_step(vector<vector<int>>& grid) {//O(mn) //is_quarantined?\n    int m=grid.size(),n=grid[0].size();\n    bool any_infection=0, fully_filled=1;\n    vector<pii> todo;\n    for (int i=0;i<m;i++) for (int j=0;j<n;j++) {\n        if (grid[i][j]==1) { //infected\n            any_infection=1;\n            for (int k=0;k<4;k++) { \n                int x_=i+dx[k], y_=j+dy[k];\n                if (x_>=0&&x_<m&&y_>=0&&y_<n&&grid[x_][y_]==0) todo.push_back({x_,y_});\n            }\n        }\n        if (fully_filled&&grid[i][j]==0)fully_filled=0;\n    }\n    for (auto _:todo)grid[_.F][_.S]=1;\n    return !any_infection || fully_filled;\n}\n\nclass cluster {\npublic:\n    set<pii> infected;\n    set<pii> conn_uninfected;\n    int wallcnt=0;\n};\n\nvoid dfs(int x, int y, vector<vector<int>>& grid, cluster &comp, vector<vector<bool>> &vis) {//O(mn)\n    int m=grid.size(),n=grid[0].size();\n    if (x<0||x>=m||y<0||y>=n||vis[x][y]||grid[x][y]==2)return;\n\n    if (grid[x][y]==0) {\n        comp.conn_uninfected.insert({x,y});\n        comp.wallcnt++;\n        return;\n    }\n    comp.infected.insert({x,y});\n    vis[x][y]=1;\n    for (int i=0;i<4;i++) {\n        int x_=x+dx[i],y_=y+dy[i];\n        dfs(x_,y_,grid,comp,vis);\n    }\n}\n\nvector<cluster> get_infected_components(vector<vector<int>>& grid) { //O(mn)\n    vector<cluster> ans;\n    int m=grid.size(),n=grid[0].size();\n    vector<vector<bool>> vis;vis.assign(m,vector<bool>(n,0));\n    for (int i=0;i<m;i++) for (int j=0;j<n;j++) {\n        if (grid[i][j]==1 && !vis[i][j]) {\n            cluster comp; \n            dfs(i,j,grid,comp,vis);\n            ans.push_back(comp);\n        }\n    }\n    return ans;\n}\npublic:\nint containVirus(vector<vector<int>>& grid) {\n    int walls=0;\n    do {\n        auto comps=get_infected_components(grid);\n        int max_index=0;\n        for (int i=0;i<comps.size();i++)\n            if (comps[max_index].conn_uninfected.size()<comps[i].conn_uninfected.size())max_index=i;\n        if (comps.size()) {\n            walls+=comps[max_index].wallcnt;\n            for (auto _:comps[max_index].infected) grid[_.F][_.S]=2;\n        }\n    } while (!simulate_step(grid));\n    return walls;\n}\n\n};\n```
['C++']