Python Hard
\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        M, N = len(isInfected), len(isInfected[0])\n        directions = [(0
```\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        M, N = len(isInfected), len(isInfected[0])\n        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n        marked = defaultdict(set)\n        walls = 0\n\n        def bfs(x, y):\n            q = deque([(x, y)])\n            s = set()\n            s.add((x, y))\n            seen.add((x, y))\n\n            while q:\n                x, y = q.popleft()\n\n                for dx, dy in directions:\n                    nx, ny = x + dx, y + dy\n  \n                    if not (0 <= nx < M) or not (0 <= ny < N):\n                        continue\n                    \n                    if (nx, ny) in seen or isInfected[nx][ny] == 0:\n                        continue\n                    \n                    if (x, y) in marked[(nx, ny)]:\n                        continue\n\n                    seen.add((nx, ny))\n                    s.add((nx, ny))\n                    q.append((nx, ny))\n\n            return s\n\n\n        while True:\n\n            groups = []\n            seen = set()\n            check = True\n        \n            for i in range(M):\n                for j in range(N):\n                    if not isInfected[i][j]:\n                        check = False\n                        continue\n\n                    if (i, j) in seen:\n                        continue\n\n                    s = bfs(i, j)\n                    groups.append(s)\n            \n            if check:\n                return walls\n            \n            if not groups:\n                return walls\n\n            total_walls = []\n            \n            for g in groups:\n                w, t = 0, set()\n                for x, y in g:\n\n                    for dx, dy in directions:\n                        nx, ny = x + dx, y + dy\n\n                        if not (0 <= nx < M) or not (0 <= ny < N):\n                            continue\n\n                        if (x, y) in marked[(nx, ny)]:\n                            continue\n\n                        if (nx, ny) in marked[(x, y)]:\n                            continue\n\n                        if isInfected[nx][ny] == 0:\n                            t.add((nx, ny))\n                            w += 1\n                            \n                total_walls.append((w, len(t)))\n            \n\n            i, mx = -1, -1\n\n            for index, (w, t) in enumerate(total_walls):\n                if t >= mx:\n                    mx = t\n                    i = index\n\n            if mx == 0:\n                return walls\n\n            walls += total_walls[i][0]\n\n            for x, y in groups[i]:\n                for dx, dy in directions:\n                    nx, ny = x + dx, y + dy\n\n                    if not (0 <= nx < M) or not (0 <= ny < N):\n                        continue\n \n                    if isInfected[nx][ny] == 0:\n                        marked[(nx, ny)].add((x, y))\n                        marked[(x, y)].add((nx, ny))\n\n\n\n            for index, g in enumerate(groups):\n                if index == i:\n                    continue\n\n                for x, y in g:\n                    for dx, dy in directions:\n                        nx, ny = x + dx, y + dy\n\n                        if not (0 <= nx < M) or not (0 <= ny < N):\n                            continue\n                        \n                        if (x, y) in marked[(nx, ny)]:\n                            continue\n\n                        isInfected[nx][ny] = 1\n\n\n        \n        return walls\n                \n\n\n                        \n\n            \n\n\n\n        \n\n\n\n        \n\n\n\n\n\n\n        \n```
['Python3']