Coding - Infection Spread Simulation

Infection Spread Simulation

Problem Statement: Given a grid of cells, each cell can either be empty or infected. Initially, some cells are infected and after a certain number of steps, we want to simulate the spread of the infection. Each step, every infected cell will infect its adjacent cells (up, down, left, right). If a cell is already infected, it remains infected. If a cell is empty and not adjacent to any infected cells, it remains empty. After a certain number of steps, return the state of the grid.

Examples:

1. Input: grid = [ [0, 1, 0], [0, 1, 0], [0, 0, 0] ], steps = 1 Output: [ [0, 0, 0], [0, 1, 1], [0, 1, 0] ]

2. Input: grid = [ [1, 1, 0], [0, 0, 1], [1, 0, 1] ], steps = 2 Output: [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]

Constraints:

1. 1 <= len(grid) <= 500
2. 1 <= len(grid[0]) <= 500
3. 0 <= grid[i][j] <= 1
4. 0 <= steps <= 500

Hints:

1. Use a queue to keep track of infected cells and their neighbors.
2. Consider using a visited set to avoid re-processing cells.

Solution: `python from collections import deque

def infectionSpread(grid, steps): if not grid or not grid[0]: return []

rows, cols = len(grid), len(grid[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
queue = deque()
visited = set()

for i in range(rows):
    for j in range(cols):
        if grid[i][j] == 1:
            queue.append((i, j))
            visited.add((i, j))

for _ in range(steps):
    size = len(queue)
    for _ in range(size):
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in visited and grid[nx][ny] == 0:
                queue.append((nx, ny))
                visited.add((nx, ny))
                grid[nx][ny] = 1

return grid

`

This solution uses a queue to keep track of infected cells and their neighbors, and a visited set to avoid re-processing cells. It simulates the spread of infection for the given number of steps and returns the final state of the grid.