DFS + heap
Intuition\n Describe your first thoughts on how to solve this problem. \n\nPython version of this.\n\n# Code\npython\nfrom heapq import heappush\n\nclass Cluste
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nPython version of [this](https://leetcode.com/problems/contain-virus/solutions/847507/cpp-dfs-solution-explained).\n\n# Code\n```python\nfrom heapq import heappush\n\nclass Cluster:\n    def __init__(self):\n        self.wall_cnt = 0\n        self.cells = set()\n        self.neighbors = set()\n    \n    def __lt__(self, other):\n        return len(self.neighbors) >= len(other.neighbors)\n\nclass Solution:\n    def dfs(self, i, j, c, seen, isInfected):\n        if i >= len(isInfected) or i < 0 or j >= len(isInfected[0]) or j < 0 or (i, j) in seen or isInfected[i][j] == -1:\n            return\n        if isInfected[i][j] == 0:\n            c.wall_cnt += 1\n            c.neighbors.add((i, j))\n            return\n        \n        c.cells.add((i, j))\n        seen.add((i, j))\n        self.dfs(i, j + 1, c, seen, isInfected)\n        self.dfs(i, j - 1, c, seen, isInfected)\n        self.dfs(i + 1, j, c, seen, isInfected)\n        self.dfs(i - 1, j, c, seen, isInfected)\n\n\n\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        ans = 0\n        m, n = len(isInfected), len(isInfected[0])\n        h = []\n\n        while True:\n            seen = set()\n            h = []\n            for i in range(m):\n                for j in range(n):\n                    if (i, j) not in seen and isInfected[i][j] == 1:\n                        c = Cluster()\n                        self.dfs(i, j, c, seen, isInfected)\n                        heappush(h, c)\n            \n            if not h:\n                break\n\n            c = heappop(h)\n            for i, j in c.cells:\n                isInfected[i][j] = -1\n            \n            ans += c.wall_cnt\n\n            while h:\n                c = heappop(h)\n                for i, j in c.neighbors:\n                    isInfected[i][j] = 1\n    \n        return ans\n```
['Python3']