readable iterative dfs solution beats 95%
Intuition\n Describe your first thoughts on how to solve this problem. \nDivide problem into subproblems, create functions for each subproblem\nput these functi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDivide problem into subproblems, create functions for each subproblem\nput these functions in global scope so that code is readable\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nkeep track of freezed cells (excluded) instead of keeping track of placed walls\n\n\n# Code\n```python3 []\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        walls_needed = 0\n        excluded = set()\n\n        while True:\n            components = scan(isInfected, excluded)\n\n            threatened_cells = threats(components, isInfected, excluded)\n            mx = -1, -1\n            for i in range(len(threatened_cells)):\n                if threatened_cells[i] > mx[0]:\n                    mx = threatened_cells[i], i\n            if mx[1] == -1:\n                return 0\n            for c_y, c_x in components[mx[1]]:\n                excluded.add((c_y, c_x))\n\n            walls_needed += calculate_walls_needed(components[mx[1]], isInfected)\n            does_spread = simulate(components, isInfected, excluded)\n            if not does_spread: break\n\n        return walls_needed\n\n\ndef scan(is_infected, excluded):\n    hei, wid = len(is_infected), len(is_infected[0])\n    vis = [[False] * wid for _ in range(hei)]\n    components = []\n\n    for y in range(hei):\n        for x in range(wid):\n            if not is_infected[y][x] or vis[y][x] or (y, x) in excluded: continue\n            stack = [(y, x)]\n            component = []\n            while stack:\n                anc_y, anc_x = stack.pop()\n                if (anc_y, anc_x) in excluded: continue\n                component.append((anc_y, anc_x))\n                vis[anc_y][anc_x] = True\n                for dy, dx in zip((1, 0, -1, 0), (0, -1, 0, 1)):\n                    if not (0 <= anc_y + dy < hei and 0 <= anc_x + dx < wid and is_infected[anc_y + dy][anc_x + dx]):\n                        continue\n                    if vis[anc_y + dy][anc_x + dx]: continue\n                    vis[anc_y + dy][anc_x + dx] = True\n                    stack.append((anc_y + dy, anc_x + dx))\n            components.append(component)\n    return components\n\n\ndef threats(components, is_infected, excluded):\n    hei, wid = len(is_infected), len(is_infected[0])\n    threatened = [0] * len(components)\n    for i in range(len(components)):\n        counted = set()\n        for c_y, c_x in components[i]:\n            if (c_y, c_x) in excluded: break\n            for dy, dx in zip((1, 0, -1, 0), (0, -1, 0, 1)):\n                if not (0 <= c_y + dy < hei and 0 <= c_x + dx < wid): continue\n                if is_infected[c_y + dy][c_x + dx]: continue\n                if (c_y + dy, c_x + dx) in counted: continue\n                threatened[i] += 1\n                counted.add((c_y + dy, c_x + dx))\n    return threatened\n\n\ndef simulate(components, is_infected, excluded):\n    hei, wid = len(is_infected), len(is_infected[0])\n    spread = False\n    for i in range(len(components)):\n        for c_y, c_x in components[i]:\n            if (c_y, c_x) in excluded: continue\n            for dy, dx in zip((1, 0, -1, 0), (0, -1, 0, 1)):\n                if not (0 <= c_y + dy < hei and 0 <= c_x + dx < wid): continue\n                if is_infected[c_y + dy][c_x + dx]: continue\n                is_infected[c_y + dy][c_x + dx] = 1\n                spread = True\n    return spread\n\n\ndef calculate_walls_needed(component, is_infected):\n    hei, wid = len(is_infected), len(is_infected[0])\n    walls = 0\n\n    for c_y, c_x in component:\n        for dy, dx in zip((1, 0, -1, 0), (0, -1, 0, 1)):\n            if not (0 <= c_y + dy < hei and 0 <= c_x + dx < wid): continue\n            if not is_infected[c_y + dy][c_x + dx]:\n                walls += 1\n    return walls\n```
['Array', 'Depth-First Search', 'Matrix', 'Simulation', 'Python3']