DFS + Heap
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n    # isInfected: 0 for uninfected; 1 for infected; -1 for contained;\n  
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n    # isInfected: 0 for uninfected; 1 for infected; -1 for contained;\n    # use DFS to traverse the whole board to find \n    # - the infected area (any cell);\n    # - its risky cells;\n    # - the number of walls needed to contain it\n    # make the risky cells array a heap:\n    # - single out the area with max risky cells\n    # - mark the rest of the risky cell infected\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n\n        # return number of walls needed\n        def dfs(r, c):\n\n            # return\n            if (r, c) in visited or r < 0 or c < 0 or r >= m or c >= n:\n                return 0\n\n            # contained cells\n            if isInfected[r][c] == -1:\n                return 0\n            \n            # uninfected cells\n            if isInfected[r][c] == 0:\n                risky.add((r, c))\n                return 1\n            \n            # infected cells\n            visited.add((r ,c))\n            walls = 0\n            if isInfected[r][c] == 1:\n                walls += dfs(r+1, c)\n                walls += dfs(r-1, c)\n                walls += dfs(r, c+1)\n                walls += dfs(r, c-1)\n\n            return walls\n        \n        m, n = len(isInfected), len(isInfected[0])\n        total_wall = 0\n\n        while True:\n            # store (len(risky), risky, wall, starting points)\n            gettingInfected = []\n            visited = set()\n            for i in range(m):\n                for j in range(n):\n                    if isInfected[i][j] == 1 and isInfected[i][j] not in visited:\n                        risky = set()\n                        w = dfs(i, j)\n                        gettingInfected.append((-len(risky), risky, w, i, j))\n\n            \n            # heapy the gettingInfectious array to get the max len of risky\n            heapq.heapify(gettingInfected)\n\n            if not gettingInfected or gettingInfected[0][2] == 0:\n                return total_wall\n\n            # mark the infected cells as contained starting from (i, j)\n            lr, risky, w, i, j = heapq.heappop(gettingInfected)\n            # maybe a dfs for marking the cells?\n            queue = collections.deque([(i, j)])\n            while queue:\n                r, c = queue.pop()\n                if r < 0 or c < 0 or r >= m or c >= n or isInfected[r][c] != 1:\n                    continue\n\n                isInfected[r][c] = -1\n\n                queue.append((r+1, c))\n                queue.append((r-1, c))\n                queue.append((r, c+1))\n                queue.append((r, c-1))\n\n            # increment the total walls\n            total_wall += w\n            for area in gettingInfected:\n                riskyCells = area[1]\n                for cell in riskyCells:\n                    r, c = cell\n                    isInfected[r][c] = 1\n\n```
['Python3']