749: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\nm, n = len(mat), len(mat[0])\nDIRECTIONS = [(-1, 0), (1, 0), (0, -1), (
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n```\nm, n = len(mat), len(mat[0])\nDIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n```\nm and n capture the dimensions of the matrix.\nDIRECTIONS is a list of four possible moves from a cell: up, down, left, and right.\n\n```\ndef dfs(i, j, visited):\n```\n\nThis function explores an infected region starting from cell (i, j) and computes:\n\nThe set of uninfected cells that can be infected by this region.\nThe number of walls needed to quarantine this region.\nThe function uses a DFS strategy and recursively explores all connected infected cells.\n\n```\ndef quarantine(i, j):\n```\n\nThis function sets all cells in an infected region (starting from (i, j)) to a state \'2\', indicating that they have been quarantined.\n\nMain Loop:\nThe main logic resides in a loop that runs until all infected regions are quarantined.\n\nvisited keeps track of the cells that have been already processed.\nregions stores details about each infected region (set of cells it can infect, number of walls to quarantine it, and a representative cell).\nEach round:\n\nFind all infected regions and the cells they can infect.\nChoose the region that can infect the maximum number of cells and quarantine it.\nLet the other regions infect their neighboring cells.\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, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n        \n        def dfs(i, j, visited):\n            if not (0 <= i < m and 0 <= j < n) or (i, j) in visited:\n                return set(), 0\n            if mat[i][j] == 2:\n                return set(), 0\n            elif mat[i][j] == 0:\n                return {(i, j)}, 1\n            \n            visited.add((i, j))\n            infected, walls = set(), 0\n            for dx, dy in DIRECTIONS:\n                ni, nj = i + dx, j + dy\n                next_infected, next_walls = dfs(ni, nj, visited)\n                infected |= next_infected\n                walls += next_walls\n            return infected, walls\n        \n        def quarantine(i, j):\n            if 0 <= i < m and 0 <= j < n and mat[i][j] == 1:\n                mat[i][j] = 2\n                for dx, dy in DIRECTIONS:\n                    quarantine(i + dx, j + dy)\n        \n        ans = 0\n        while True:\n            visited, regions = set(), []\n            for i in range(m):\n                for j in range(n):\n                    if mat[i][j] == 1 and (i, j) not in visited:\n                        infected, walls = dfs(i, j, visited)\n                        if infected:\n                            regions.append((infected, walls, (i, j)))\n            \n            if not regions:\n                break\n            \n            regions.sort(key=lambda x: (-len(x[0]), x[1]))\n            max_infected, max_walls, start = regions[0]\n            ans += max_walls\n            quarantine(*start)\n            \n            for region in regions[1:]:\n                for i, j in region[0]:\n                    mat[i][j] = 1\n        \n        return ans\n\n```
['Array', 'Depth-First Search', 'Breadth-First Search', 'Matrix', 'Simulation', 'Python', 'Python3']