Solution
C++ []\nint mp[2652], *zp[2652], zc[2652], step, mk;\n\nint dfs(int *p) {\n    *p = 2;\n    int res = 0;\n    for (int *nb : {p-step, p-1, p+1, p+step}) {\n    
```C++ []\nint mp[2652], *zp[2652], zc[2652], step, mk;\n\nint dfs(int *p) {\n    *p = 2;\n    int res = 0;\n    for (int *nb : {p-step, p-1, p+1, p+step}) {\n        int v = *nb;\n        if (v == mk || v > 1) continue;\n        if (v <= 0) *nb = mk, ++res; else res += dfs(nb);\n    }\n    return res;\n}\nint dfs2(int *p) {\n    *p = 1000;\n    int res = 0;\n    for (int *nb : {p-step, p-1, p+1, p+step}) {\n        int v = *nb;\n        if (v == 2) res += dfs2(nb); else if (v <= 0) ++res, *nb = 0;\n    }\n    return res;\n}\nvoid dfs3(int *p) {\n    *p = 1;\n    for (int *nb : {p-step, p-1, p+1, p+step}) {\n        int v = *nb;\n        if (v == 2) dfs3(nb); else if (v <= 0) *nb = 1;\n    }\n}\nclass Solution {\npublic:\n    int containVirus(vector<vector<int>>& isInfected) {\n        step = isInfected[0].size() + 1; mk = 0;\n        {\n            int *p = mp+step;\n            fill(mp, p, 1000);\n            for (const auto &r : isInfected) {\n                for (int x : r) *p++ = x;\n                *p++ = 1000;\n            }\n            fill(p, p+step, 1000);\n        }\n        int *lo = mp+step, *hi = lo + step*isInfected.size(), res = 0;\n        while(1) {\n            int nb = 0;\n            for (int *p = lo; p != hi; ++p) if (*p == 1) zp[nb] = p, --mk, zc[nb++] = dfs(p);\n            if (nb == 0) break;\n\n            int best = 0;\n            for (int i = 1; i < nb; ++i) if (zc[i] > zc[best]) best = i;\n            if (!zc[best]) break;\n            res += dfs2(zp[best]);\n\n            for (int *p = lo; p != hi; ++p) if (*p == 2) dfs3(p);\n        }\n        return res;\n    }\n};\n```\n\n```Python3 []\nimport math\n\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n\n        def traverse_infected(r,c):\n\n            q = [(r,c)]\n            infected_cells = set(q)\n            perimeter = 0\n            bordering_cells = set()\n\n            while len(q) > 0:\n                next_iter = []\n\n                for r,c in q:\n                    neighbors = [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]\n                    for adj_r,adj_c in neighbors:\n                        if m > adj_r >= 0 and n > adj_c >= 0:\n                            if isInfected[adj_r][adj_c] == 1:\n                                if (adj_r,adj_c) not in infected_cells:\n                                    infected_cells.add((adj_r,adj_c))\n                                    next_iter.append((adj_r,adj_c))\n                            elif isInfected[adj_r][adj_c] == 0:\n                                perimeter += 1\n                                bordering_cells.add((adj_r,adj_c))\n                q = next_iter\n            \n            return infected_cells,bordering_cells,perimeter\n        \n        m,n = len(isInfected),len(isInfected[0])\n\n        walls = 0\n        while 1:\n            all_infected_cells = set()\n\n            most_threatening = (0, None)\n\n            regions_this_iter = []\n            i = 0\n            for r in range(m):\n                for c in range(n):\n                    if isInfected[r][c] == 1 and (r,c) not in all_infected_cells:\n                        infected_region,region_borders,perimeter = traverse_infected(r,c)\n\n                        regions_this_iter.append((infected_region,region_borders,perimeter))\n\n                        if len(region_borders) > most_threatening[0]:\n                            most_threatening = (len(region_borders), i)\n                        \n                        all_infected_cells.update(infected_region)\n                        i += 1\n            \n            if most_threatening[0] != 0:\n                walls += regions_this_iter[most_threatening[1]][2]\n                for r,c in regions_this_iter[most_threatening[1]][0]:\n                    isInfected[r][c] = 2\n                \n                for i in range(len(regions_this_iter)):\n                    if i != most_threatening[1]:\n                        for r,c in regions_this_iter[i][1]:\n                            isInfected[r][c] = 1\n            else:\n                break\n        return walls\n```\n\n```Java []\nclass Solution {\n    class Region {\n        Set<Integer> infected = new HashSet<>();\n        Set<Integer> unInfected = new HashSet<>();\n        int walls = 0;\n    } \n    public int containVirus(int[][] isInfected) {\n        int ans = 0;\n        int re = isInfected.length;\n        int ce = isInfected[0].length;\n\n        while (true) {\n            List<Region> holder = new ArrayList<>();\n            boolean[][] v = new boolean[re][ce];\n            for (int r = 0; r < re; r++) {\n                for (int c = 0; c < ce; c++) {\n                    if (isInfected[r][c] == 1 && !v[r][c]) {\n                        Region region = new Region();\n                        getRegion(isInfected, region, re, ce, v, r, c);\n                        holder.add(region);\n                    }\n                }\n            }\n            int indexOfMaxUnInfected = 0;\n            int sizeOfMaxUnInfected = 0;\n            for (int i = 0; i < holder.size(); i++) {\n                Region region = holder.get(i);\n\n                if (region.unInfected.size() > sizeOfMaxUnInfected) {\n                    sizeOfMaxUnInfected = region.unInfected.size();\n                    indexOfMaxUnInfected = i;\n                }\n            }\n            if (holder.size() == 0) {\n                break;\n            }\n            Set<Integer> maxSet = holder.get(indexOfMaxUnInfected).infected;\n            for (int rowCol : maxSet) {\n                int r = rowCol / ce;\n                int c = rowCol % ce;\n                isInfected[r][c] = 2;\n            }\n            ans += holder.get(indexOfMaxUnInfected).walls;\n            for (int i = 0; i < holder.size(); i++) {\n                \n                if (i == indexOfMaxUnInfected) {\n                    continue;\n                }\n                Region region = holder.get(i);\n                Set<Integer> unInfected = region.unInfected;\n\n                for (int rowCol : unInfected) {\n                    int r = rowCol / ce;\n                    int c = rowCol % ce;\n                    isInfected[r][c] = 1;\n                }\n            }\n        }\n        return ans;\n    }\n    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n    private void getRegion(int[][] isInfected, Region region, int re, int ce, \n        boolean[][] v, int r, int c) {\n        if (r < 0 || c < 0 || r == re || c == ce || isInfected[r][c] == 2) {\n            return;\n        }\n        if (isInfected[r][c] == 1) {\n            if (v[r][c]) {\n                return;\n            }\n            region.infected.add(r * ce + c);\n        }\n        if (isInfected[r][c] == 0) {\n            region.unInfected.add(r * ce + c);\n            region.walls++;\n            return;\n        }\n        v[r][c] = true;\n        for (int[] dir : dirs) {\n            int nr = r + dir[0];\n            int nc = c + dir[1];\n            getRegion(isInfected, region, re, ce, v, nr, nc);\n        }\n    }\n}\n```\n
['C++', 'Java', 'Python3']