[C++] 4ms DFS beats 100%
\npublic:\n    int containVirus(vector<vector<int>>& grid) {\n        while (build_wall(grid)) {}\n        return res;\n    }\n    \nprivate:\n    int res = 0;\
```\npublic:\n    int containVirus(vector<vector<int>>& grid) {\n        while (build_wall(grid)) {}\n        return res;\n    }\n    \nprivate:\n    int res = 0;\n    int dfs(vector<vector<int>>& grid, int i, int j, int k, int& wall, vector<vector<int>>& infected_grid) {\n        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] < 0) return 0;\n        if (grid[i][j] == k) {\n            if (infected_grid[i][j] > 0) wall++; // only build wall on boundary\n            return 0;\n        }\n        \n        if (grid[i][j] == 1) {\n            grid[i][j] = k; // grid[i][j] = 1 -> k, not boundary, don\'t build wall\n            return dfs(grid, i + 1, j, k, wall, infected_grid) + dfs(grid, i, j + 1, k, wall, infected_grid)\n                 + dfs(grid, i - 1, j, k, wall, infected_grid) + dfs(grid, i, j - 1, k, wall, infected_grid);\n        }\n        \n        grid[i][j] = k; // grid[i][j] = 0 -> k\n        infected_grid[i][j]++; // record the boundary\n        wall++; // only build wall on boundary\n        return 1;\n    }\n    \n    bool build_wall(vector<vector<int>>& grid) {\n        int k = 1, m = grid.size(), n = grid[0].size(), max_infected = -1, K = 0, add_wall = 0;\n        vector<vector<int>> infected_grid(m, vector<int>(n, 0));\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == 1) {\n                    int wall = 0, infected = dfs(grid, i, j, ++k, wall, infected_grid);\n                    if (max_infected < infected) {\n                        max_infected = infected;\n                        add_wall = wall;\n                        K = k;\n                    }\n                }\n            }\n        }\n        \n        if (k == 1) return false; // no free infected area exists, stop\n        \n        res += add_wall;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] > 0) grid[i][j] = (grid[i][j] == K && infected_grid[i][j] <= 1) ? infected_grid[i][j] - 1 : 1; // set area inside new wall as -1, else where as 1\n            }\n        }\n        return true;\n    }\n```
[]