# Zombie in Matrix

BFS

## # Input & Output

@param grid: a 2D integer grid
@return: an integer

1
2

## # Solution

Let $n$ be the number of rows and $m$ be the number of columns.

### # Layered BFS

Note that queue is initialized with multiple points.

Complexity

time: $O(V + E) = O(nm)$
space: $O(V + E) = O(nm)$

DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def zombie(self, grid):
n, m = len(grid), len(grid[0])
queue = []
res = 0

# initialize queue
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
queue.append((i, j))

# layered BFS
while queue:
res += 1
for i in range(len(queue)):
x, y = queue.pop(0)
for dx, dy in DIRECTIONS:
nx, ny = x+dx, y+dy
if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 0:
grid[nx][ny] = 1
queue.append((nx, ny))

# check if all people are turned into zombies
for i in range(n):
for j in range(m):
if grid[i][j] == 0:
return -1

# minus the extra step
return res-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31