Simulation - BFS
Code\ncpp []\nclass Solution {\npublic:\n    int drow[4] = {-1,0,1,0};\n    int dcol[4] = {0,1,0,-1};\n    int no_of_cells_infected(vector<vector<int>> &grid,in
# Code\n```cpp []\nclass Solution {\npublic:\n    int drow[4] = {-1,0,1,0};\n    int dcol[4] = {0,1,0,-1};\n    int no_of_cells_infected(vector<vector<int>> &grid,int row,int col,vector<vector<int>> &vis,vector<vector<int>> &already){\n        vis[row][col] = 1;\n        queue<pair<int,int>> q;\n        q.push({row,col});\n        vector<pair<int,int>> l;\n        int cnt = 0;\n        while(!q.empty()){\n            auto it = q.front();\n            int r = it.first;\n            int c = it.second;\n            q.pop();\n            for(int i=0;i<4;i++){\n                int nrow = r + drow[i];\n                int ncol = c + dcol[i];\n                if(nrow >= 0 && nrow < grid.size() && ncol >= 0 && ncol < grid[0].size() && !vis[nrow][ncol] && !already[nrow][ncol]){\n                    if(grid[nrow][ncol]) q.push({nrow,ncol});\n                    else{\n                        cnt++;\n                        l.push_back({nrow,ncol});\n                    }\n                    vis[nrow][ncol] = 1;\n                }\n            }\n        }\n        for(auto it: l) vis[it.first][it.second] = 0;\n        return cnt;\n    }\n    pair<int,int> find_area(vector<vector<int>> &grid,vector<vector<int>> &already){\n        int n = grid.size(); int m = grid[0].size();\n        pair<int,int> pair = {-1,-1}; int maxi = 0;\n        vector<vector<int>> vis(n,vector<int>(m,0));\n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                if(grid[i][j] && !already[i][j] && !vis[i][j]){\n                    int tmp = maxi;\n                    maxi = max(no_of_cells_infected(grid,i,j,vis,already),maxi);\n                    if(tmp != maxi) pair = {i,j};\n                }\n            }\n        }\n        return pair;\n    }\n    int containVirus(vector<vector<int>>& grid) {\n        int n = grid.size(); int m = grid[0].size();\n        vector<vector<int>> vis(n,vector<int>(m,0));\n        int cnt = 0;\n        while(true){\n            pair<int,int> coor = find_area(grid,vis);\n            if(coor.first == -1 || coor.second == -1) break;\n            cnt += make_walls(grid,vis,coor.first,coor.second);\n            update_grid(grid,vis);\n        }\n        return cnt;\n    }\n    int make_walls(vector<vector<int>> &grid, vector<vector<int>> &vis, int start_row, int start_col){\n        int n = grid.size(); int m = grid[0].size();\n        vis[start_row][start_col] = 1;\n        queue<pair<int,int>> q;\n        q.push({start_row,start_col});\n        int cnt = 0;\n        while(!q.empty()){\n            auto it = q.front();\n            int row = it.first;\n            int col = it.second;\n            q.pop();\n            for(int i=0;i<4;i++){\n                int nrow = row + drow[i];\n                int ncol = col + dcol[i];\n                if(nrow >= 0 && ncol >= 0 && nrow < n && ncol < m && !vis[nrow][ncol]){\n                    if(grid[nrow][ncol]){\n                        vis[nrow][ncol] = 1;\n                        q.push({nrow,ncol});\n                    }else cnt++;\n                }\n            }\n        }\n        return cnt;\n    }\n    void update_grid(vector<vector<int>> &grid,vector<vector<int>> &vis){\n        int n = grid.size(); int m = grid[0].size();\n        vector<vector<int>> vis_comp(n,vector<int>(m,0));\n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                if(grid[i][j] && !vis_comp[i][j] && !vis[i][j]){ // is one and not a newly added cell and not walled one\n                    for(int l=0;l<4;l++){\n                        int nrow = i + drow[l];\n                        int ncol = j + dcol[l];\n                        if(nrow >= 0 && ncol >= 0 && nrow < n && ncol < m && !vis_comp[nrow][ncol] && !grid[nrow][ncol] && !vis[nrow][ncol]){\n                            grid[nrow][ncol] = 1;\n                            vis_comp[nrow][ncol] = 1;\n                        }\n                    }\n                }\n            }\n        }\n    }\n};\n```
['Breadth-First Search', 'Matrix', 'Simulation', 'C++']