Commented Python using DFS with explanation
Find most threatening region (would infect most normal cells next night) via DFS and at same time count the walls needed to wall off, and return it\'s coordinat
1. Find most threatening region (would infect most normal cells next night) via DFS and at same time count the walls needed to wall off, and return it\'s coordinates\n2. Quarantine that region by doing DFS and walling that region off by setting 1\'s to -1\'s\n3. Simulate night virus spread: find a \'1\' do a DFS on it and set perimeter empty spaces to 2. Once done this for all cells, set 2\'s to 1. This is so that while iterating it doesn\'t see newly infected cells as cells next to the empty perimeter (then it would spread all in one night)\n\nRT: O(M*N * infected_regions)\nSpc: O(M*N) (could be a deep DFS)\n\n```\n    def containVirus(self, grid):\n        dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n\n        def cells():\n            for r in range(R):\n                for c in range(C):\n                    yield (r, c)\n\n        def is_valid(i, j):\n            return 0 <= i < R and 0 <= j < C\n\n        def neighbours(r, c):\n            """Get valid neighbour cells"""\n            for dr, dc in dirs:\n                if is_valid(r+dr, c+dc):\n                    yield (r+dr, c+dc)\n\n        def pick_most_threatening_region():\n            visited = set()\n\n            def dfs(r, c):\n                """Returns number of walls needed to quarantine infected region\n                starting at (r,c)"""\n                # Avoid already visited or quarantined cells.\n                if (r, c) in visited or grid[r][c] == -1:\n                    return 0\n                # Found an empty perimeter space\n                if grid[r][c] == 0:\n                    perimeter.add((r, c))\n                    # Counts as one wall needed to contain infected cell.\n                    return 1\n                \n                visited.add((r, c))\n                # Explore neighbours and return the sum of the walls needed to\n                # contain their perimeter.\n                return sum(dfs(nr, nc) for (nr, nc) in neighbours(r, c))\n\n            max_perimeter, max_p_walls, max_start = 0, 0, (0, 0)\n            for r, c in cells():\n                # Find cells that have not yet been visited and are infected.\n                if (r, c) not in visited and grid[r][c] == 1:\n                    perimeter = set()\n                    # Get the total walls needed to quarantine the infected region.\n                    walls = dfs(r, c)\n                    # If the parameter we could save is the biggest we\'ve seen...\n                    if len(perimeter) > max_perimeter:\n                         # update the walls needed to quarantine, and an infected cell\n                         # from which we might mark the infected region as quarantined (setting -1)\n                        max_perimeter, max_p_walls, max_start = len(perimeter), walls, (r, c)\n            return max_p_walls, max_start\n\n        def quarantine(r, c):\n            """Mark an infected region as quarantined by setting cells to -1"""\n            grid[r][c] = -1\n            # Explore neighbours to quarantine them too.\n            for nr, nc in neighbours(r, c):\n                if grid[nr][nc] == 1:\n                    quarantine(nr, nc)\n                \n        def simulate_night():\n            """Spreads the infection by one night of non-quarntined regions."""\n            \n            def infected_neighbour(r, c):\n                """Returns True if an orthogonally adjacent square is infected."""\n                return any(grid[nr][nc] == 1 for nr, nc in neighbours(r, c))\n \n            for r, c in cells():\n                # Find clean cells that are next to infected cells\n                if grid[r][c] == 0 and infected_neighbour(r, c):\n                    # Set them temporarily to 2, so that further iterations do not\n                    # count them as infected (otherwise it would spread endlessly\n                    # in one night).\n                    grid[r][c] = 2\n            \n            # Go over a second time and set the temporarily marked newly infected cells\n            # to permanently infected.\n            for r, c in cells():\n                if grid[r][c] == 2:\n                    grid[r][c] = 1\n\n        if not grid or not grid[0]:\n            return 0\n        R, C = len(grid), len(grid[0])\n\n        walls = 0\n        while True:\n            new_walls, (r, c) = pick_most_threatening_region()\n            # Stop when there are no more infected regions, i.e. only\n            # -1 (quarantined by us) and 0\'s are left.\n            if new_walls == 0:\n                return walls\n            quarantine(r, c)\n            walls += new_walls\n            simulate_night()\n        return walls\n```
[]