Python BFS Clean Approach (beats 100% solutions)
\n Describe your approach to solving the problem. \n\n# Approach\n\n- Identify Separate Regions: Identify all infected regions and their respective boundaries.\
\n<!-- Describe your approach to solving the problem. -->\n\n# Approach\n\n- Identify Separate Regions: Identify all infected regions and their respective boundaries.\n\n- Prioritize by Threat: Determine which region poses the greatest threat by the number of uninfected cells it can potentially infect.\n\n- Contain the Most Threatening Region: Build walls around the most threatening region to contain the virus there.\n\n- Spread the Virus: Allow the virus to spread from the other regions.\n\n- Repeat: Repeat the above steps until all regions are contained.\n\n\n# Complexity\n- Time complexity: O(m*n)\n\n- Space complexity: O(m*n)\n\n# Code\n```\nclass Solution(object):\n    def containVirus(self, isInfected):\n        """\n        :type isInfected: List[List[int]]\n        :rtype: int\n        """\n        # start with infected cell and map the start of cells to \n        def get_regions():\n            visited = [[False] * n for _ in range(m)]\n            regions = []\n            frontiers = []\n            walls_needed = []\n            \n            def bfs(x, y):\n                queue = deque([(x, y)])\n                visited[x][y] = True\n                region = [(x, y)]\n                frontier = set()\n                walls = 0\n                \n                while queue:\n                    cx, cy = queue.popleft()\n                    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n                        nx, ny = cx + dx, cy + dy\n                        if 0 <= nx < m and 0 <= ny < n:\n                            if not visited[nx][ny]:\n                                if isInfected[nx][ny] == 1:\n                                    visited[nx][ny] = True\n                                    queue.append((nx, ny))\n                                    region.append((nx, ny))\n                                elif isInfected[nx][ny] == 0:\n                                    frontier.add((nx, ny))\n                                    walls += 1\n                return region, frontier, walls\n            \n            for i in range(m):\n                for j in range(n):\n                    if isInfected[i][j] == 1 and not visited[i][j]:\n                        region, frontier, walls = bfs(i, j)\n                        if region:\n                            regions.append(region)\n                            frontiers.append(frontier)\n                            walls_needed.append(walls)\n            \n            return regions, frontiers, walls_needed\n        \n        m, n = len(isInfected), len(isInfected[0])\n        total_walls = 0\n        \n        while True:\n            regions, frontiers, walls_needed = get_regions()\n            if not regions:\n                break\n            \n            # Find the region with the maximum threat\n            max_threat_index = max(range(len(frontiers)), key=lambda i: len(frontiers[i]))\n            total_walls += walls_needed[max_threat_index]\n            \n            # Contain the most threatening region\n            for x, y in regions[max_threat_index]:\n                isInfected[x][y] = -1\n            \n            # Spread the virus from other regions\n            for i in range(len(regions)):\n                if i == max_threat_index:\n                    continue\n                for x, y in frontiers[i]:\n                    isInfected[x][y] = 1\n        \n        return total_walls\n```
['Python']