Naive C++ solution using BFS
Just follow the instruction of the problem. You can run it to see the output of every stage. Hope to find a more elegant algorithm.\n\nclass Solution {\npublic:
Just follow the instruction of the problem. You can run it to see the output of every stage. Hope to find a more elegant algorithm.\n```\nclass Solution {\npublic:\n    int containVirus(vector<vector<int>>& grid) {\n        size_t row = grid.size(), col = grid[0].size();\n        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        \n        vector<vector<bool>> control = vector<vector<bool>>(row, vector<bool>(col, false));\n        int numWalls = 0;\n        while (true) {\n            vector<vector<bool>> visited = vector<vector<bool>>(row, vector<bool>(col, false));\n            vector<vector<int>> infection = vector<vector<int>>(row, vector<int>(col, 0));\n            int mostInfection = 0;\n            for (int x = 0; x < row; x++) {\n                for (int y = 0; y < col; y++) {\n                    if (!control[x][y] && !visited[x][y] && grid[x][y] == 1) {\n                        vector<vector<bool>> infectionVisited = vector<vector<bool>>(row, vector<bool>(col, false));\n                        visited[x][y] = true;\n                        int infectionSize = 0;\n                        queue<pair<int, int>> bfs;\n                        bfs.push({x, y});\n                        while (!bfs.empty()) {\n                            auto point = bfs.front();\n                            int px = point.first, py = point.second;\n                            bfs.pop();\n                            \n                            for (size_t i = 0; i < 4; i++) {\n                                int newx = px + dirs[i][0], newy = py + dirs[i][1];\n                                if (newx >= 0 && newx < row && newy >= 0 && newy < col) {\n                                    if (!control[newx][newy] && !visited[newx][newy]) {\n                                        if (grid[newx][newy] == 1) {\n                                            visited[newx][newy] = true;\n                                            bfs.push({newx, newy});\n                                        } else if (!infectionVisited[newx][newy]){\n                                            infectionVisited[newx][newy] = true;\n                                            infectionSize ++;\n                                        }\n                                    }\n                                }\n                            }\n                        }\n                        cout << "(" << x << ", " << y << ") infects: " << infectionSize << endl;\n                        infection[x][y] = infectionSize;\n                        mostInfection = max(mostInfection, infectionSize);\n                    }\n                }\n            }\n            \n            if (mostInfection == 0) {\n                break;\n            }\n            \n            for (int x = 0; x < row; x++) {\n                bool complete = false;\n                for (int y = 0; y < col; y++) {\n                    if (infection[x][y] == mostInfection) {\n                        visited = vector<vector<bool>>(row, vector<bool>(col, false));\n                        visited[x][y] = true;\n                        queue<pair<int, int>> bfs;\n                        bfs.push({x, y});\n                        while (!bfs.empty()) {\n                            auto point = bfs.front();\n                            int px = point.first, py = point.second;\n                            bfs.pop();\n                            \n                            control[x][y] = true;\n                            for (size_t i = 0; i < 4; i++) {\n                                int newx = px + dirs[i][0], newy = py + dirs[i][1];\n                                if (newx >= 0 && newx < row && newy >= 0 && newy < col) {\n                                    if (!control[newx][newy] && !visited[newx][newy]) {\n                                        if (grid[newx][newy] == 1) {\n                                            control[newx][newy] = true;\n                                            visited[newx][newy] = true;\n                                            bfs.push({newx, newy});\n                                        } else {\n                                            numWalls ++;\n                                        }\n                                    }\n                                }\n                            }\n                        }\n                        infection[x][y] = 0;\n                        complete = true;\n                        break;\n                    }\n                }\n                if (complete) {\n                    break;\n                }\n            }\n            cout << "Walls: " << numWalls << endl;\n            \n            vector<vector<int>> newGrid = grid;\n            for (int x = 0; x < row; x++) {\n                for (int y = 0; y < col; y++) {\n                    if (infection[x][y] > 0) {\n                        visited = vector<vector<bool>>(row, vector<bool>(col, false));\n                        visited[x][y] = true;\n                        queue<pair<int, int>> bfs;\n                        bfs.push({x, y});\n                        while (!bfs.empty()) {\n                            auto point = bfs.front();\n                            int px = point.first, py = point.second;\n                            bfs.pop();\n                            \n                            for (size_t i = 0; i < 4; i++) {\n                                int newx = px + dirs[i][0], newy = py + dirs[i][1];\n                                if (newx >= 0 && newx < row && newy >= 0 && newy < col) {\n                                    if (!control[newx][newy] && !visited[newx][newy]) {\n                                        if (grid[newx][newy] == 1) {\n                                            visited[newx][newy] = true;\n                                            bfs.push({newx, newy});\n                                        } else {\n                                            newGrid[newx][newy] = 1;\n                                        }\n                                    }\n                                }\n                            }\n                        }\n                    }\n                }\n            }\n            grid = newGrid;\n            for (auto line : newGrid) {\n                for (auto item : line) {\n                    cout << item << ' ';\n                }\n                cout << endl;\n            }\n            cout << "===" << endl;\n        }\n        return numWalls;\n    }\n};\n```
[]