Contain Virus Question
\n# Intuition\n- Identify Infected Regions: Use BFS or DFS to find all contiguous regions of infected cells (cells with value 1).\n\n- Calculate Threats and Wal
\n# Intuition\n- Identify Infected Regions: Use BFS or DFS to find all contiguous regions of infected cells (cells with value 1).\n\n- Calculate Threats and Walls: For each infected region, determine the number of uninfected cells it can potentially infect in the next step and calculate the number of walls needed to quarantine the region.\n\n- Select the Most Threatening Region: Choose the region that can potentially infect the most uninfected cells. This region should be quarantined by installing walls around it.\n\n- Quarantine and Spread: Quarantine the selected region by marking it so that it can no longer spread. Then, spread the virus from the remaining regions to their neighboring uninfected cells.\n\n- Repeat: Continue the above steps until no further spread is possible or all regions are quarantined.\n\n# Approach\n\nThe approach to solving the problem involves simulating the containment of the virus by installing walls to quarantine infected regions. Here\'s a detailed breakdown of the approach:\n\n**Identify Infected Regions:**\nUse Depth-First Search (DFS) or Breadth-First Search (BFS) to identify all contiguous regions of infected cells. This step helps partition the grid into separate infected regions.\n\n**Calculate Threats and Walls:**\nFor each infected region, determine the number of uninfected cells it can potentially infect in the next step. This represents the threat posed by the region.\nCalculate the number of walls needed to quarantine each region. Walls are installed on the shared boundary between infected and uninfected cells.\n\n**Select the Most Threatening Region:**\nIdentify the infected region that poses the highest threat, i.e., the region that can infect the most uninfected cells.\nPrioritize quarantining this region by installing walls around it.\n\n**Quarantine and Spread:**\nQuarantine the selected region by installing walls around it. This prevents the virus from spreading further from this region.\nLet the virus spread from other infected regions to neighboring uninfected cells. Update the infected cells accordingly.\n\n**Repeat Until Convergence:**\nRepeat the above steps until either all infected regions are quarantined or no further spread of the virus is possible.\nEach iteration involves selecting the most threatening region, quarantining it, and updating the infected cells.\n\n**Return the Total Number of Walls Used:**\nAfter containment is complete, return the total number of walls installed to quarantine all infected regions.\n\n# Complexity\n- Time complexity:\n$$O(m * n)$$\n\n- Space complexity:\n$$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        from collections import deque, defaultdict\n        \n        m, n = len(isInfected), len(isInfected[0])\n        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n        \n        def get_regions():\n            visited = [[False] * n for _ in range(m)]\n            regions = []\n            for i in range(m):\n                for j in range(n):\n                    if isInfected[i][j] == 1 and not visited[i][j]:\n                        queue = deque([(i, j)])\n                        region = []\n                        visited[i][j] = True\n                        while queue:\n                            x, y = queue.popleft()\n                            region.append((x, y))\n                            for dx, dy in directions:\n                                nx, ny = x + dx, y + dy\n                                if 0 <= nx < m and 0 <= ny < n and isInfected[nx][ny] == 1 and not visited[nx][ny]:\n                                    visited[nx][ny] = True\n                                    queue.append((nx, ny))\n                        regions.append(region)\n            return regions\n        \n        def calculate_threats(region):\n            threat_cells = set()\n            walls_needed = 0\n            for x, y in region:\n                for dx, dy in directions:\n                    nx, ny = x + dx, y + dy\n                    if 0 <= nx < m and 0 <= ny < n and isInfected[nx][ny] == 0:\n                        threat_cells.add((nx, ny))\n                        walls_needed += 1\n            return threat_cells, walls_needed\n        \n        total_walls = 0\n        while True:\n            regions = get_regions()\n            if not regions:\n                break\n            \n            max_threat_index = -1\n            max_threat_count = -1\n            threats = []\n            walls_needed = []\n            \n            for i, region in enumerate(regions):\n                threat_cells, walls = calculate_threats(region)\n                threats.append(threat_cells)\n                walls_needed.append(walls)\n                if len(threat_cells) > max_threat_count:\n                    max_threat_count = len(threat_cells)\n                    max_threat_index = i\n            \n            if max_threat_index == -1:\n                break\n            \n            total_walls += walls_needed[max_threat_index]\n            \n            for i, region in enumerate(regions):\n                if i == max_threat_index:\n                    for x, y in region:\n                        isInfected[x][y] = -1  # Quarantine the region\n                else:\n                    for x, y in threats[i]:\n                        isInfected[x][y] = 1  # Spread the virus\n        \n        return total_walls\n\n# Example usage\nsol = Solution()\nisInfected = [\n    [0,1,0,0,0,0,0,1],\n    [0,1,0,0,0,0,0,1],\n    [0,0,0,0,0,0,0,1],\n    [0,0,0,0,0,0,0,0]\n]\nprint(sol.containVirus(isInfected))  # Output: 10\n\n```
['Python']