749. Contain Virus
Intuition\nThe problem requires simulating the spread of a virus and containment efforts day by day. We need to identify the region that threatens the most unin
# Intuition\nThe problem requires simulating the spread of a virus and containment efforts day by day. We need to identify the region that threatens the most uninfected cells each day, quarantine it, and continue this process until all infected regions are contained or the entire grid is infected.\n\n# Approach\n1. Implement a function to find all distinct virus regions using DFS.\n2. For each region, calculate the number of walls needed and the number of cells it threatens.\n3. Quarantine the region that threatens the most cells by marking it with a special value.\n4. Simulate the spread of the virus in non-quarantined regions.\n5. Repeat steps 1-4 until no more spreading is possible.\n\n# Complexity\n- Time complexity: O(m * n * (m + n)), where m and n are the dimensions of the grid. In the worst case, we might need to traverse the entire grid multiple times.\n- Space complexity: O(m * n) for the recursion stack in DFS and to store the visited cells.\n\n# Code\n```python3\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        def dfs(i, j, visited, region, frontier):\n            if (i, j) in visited:\n                return 0\n            visited.add((i, j))\n            region.add((i, j))\n            walls = 0\n            for ni, nj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n                if 0 <= ni < m and 0 <= nj < n:\n                    if isInfected[ni][nj] == 1:\n                        walls += dfs(ni, nj, visited, region, frontier)\n                    elif isInfected[ni][nj] == 0:\n                        frontier.add((ni, nj))\n                        walls += 1\n            return walls\n\n        m, n = len(isInfected), len(isInfected[0])\n        total_walls = 0\n\n        while True:\n            visited = set()\n            regions = []\n            frontiers = []\n            walls = []\n\n            for i in range(m):\n                for j in range(n):\n                    if isInfected[i][j] == 1 and (i, j) not in visited:\n                        region = set()\n                        frontier = set()\n                        region_walls = dfs(i, j, visited, region, frontier)\n                        regions.append(region)\n                        frontiers.append(frontier)\n                        walls.append(region_walls)\n\n            if not regions:\n                break\n\n            max_frontier = max(range(len(frontiers)), key=lambda i: len(frontiers[i]))\n            total_walls += walls[max_frontier]\n\n            for i, region in enumerate(regions):\n                if i != max_frontier:\n                    for r, c in region:\n                        for nr, nc in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]:\n                            if 0 <= nr < m and 0 <= nc < n and isInfected[nr][nc] == 0:\n                                isInfected[nr][nc] = 1\n\n            for r, c in regions[max_frontier]:\n                isInfected[r][c] = -1\n\n        return total_walls
['Python3']