Grid Spread Timer - FAANG Problems | Repovive

FNG3. Grid Spread Timer

2s256 MB

This problem is based on an Amazon interview problem described here.

You are given an $m \times n$ grid where each cell contains either a zombie ( $1$ ) or a human ( $0$ ).

Every hour, all zombies simultaneously infect their adjacent humans. A zombie can infect the human directly up, down, left, or right of it (not diagonally).

Return the number of hours until no humans remain on the grid, or $-1$ if it is impossible (i.e., there are humans but no zombies to infect them).

Constraints

$1 \le m, n \le 500$
Each cell is $0$ or $1$ .

Input

\begin{array}{l} m \quad n \\ g_{0,0} \quad g_{0,1} \quad \cdots \quad g_{0,n-1} \\ \vdots \\ g_{m-1,0} \quad \cdots \quad g_{m-1,n-1} \end{array}

Output

$ans$

Samples

Input

Explanation

\begin{array}{l} \text{After hour } \color{red}{\text{1 :}} \\ \qquad \begin{array}{ccccc} \color{red}{1} & 1 & 1 & \color{red}{1} & 1 \\ \color{red}{1} & 1 & \color{red}{1} & 1 & \color{red}{1} \\ 0 & \color{red}{1} & 0 & \color{red}{1} & 1 \\ \color{red}{1} & 1 & \color{red}{1} & 0 & \color{red}{1} \end{array} \\ \\ \text{After hour } \color{blue}{\text{2 :}} \\ \qquad \begin{array}{ccccc} \color{red}{1} & 1 & 1 & \color{red}{1} & 1 \\ \color{red}{1} & 1 & \color{red}{1} & 1 & \color{red}{1} \\ \color{blue}{1} & \color{red}{1} & \color{blue}{1} & \color{red}{1} & 1 \\ \color{red}{1} & 1 & \color{red}{1} & \color{blue}{1} & \color{red}{1} \end{array} \end{array}

Output

Input

2 2
1 0
0 1

Explanation

\begin{array}{l} \text{After hour } \color{red}{\text{1 :}} \\ \qquad \begin{array}{cc} 1 & \color{red}{1} \\ \color{red}{1} & 1 \end{array} \\ \\ \end{array}

Output

Input

Explanation

\begin{array}{l} \text{After hour } \color{red}{\text{1 :}} \\ \qquad \begin{array}{ccc} 1 & \color{red}{1} & 0 \\ \color{red}{1} & 0 & 0 \\ 0 & 0 & 0 \end{array} \\ \\ \text{After hour } \color{blue}{\text{2 :}} \\ \qquad \begin{array}{ccc} 1 & \color{red}{1} & \color{blue}{1} \\ \color{red}{1} & \color{blue}{1} & 0 \\ \color{blue}{1} & 0 & 0 \end{array} \\ \\ \text{After hour } \color{green}{\text{3 :}} \\ \qquad \begin{array}{ccc} 1 & \color{red}{1} & \color{blue}{1} \\ \color{red}{1} & \color{blue}{1} & \color{green}{1} \\ \color{blue}{1} & \color{green}{1} & 0 \end{array} \\ \\ \text{After hour } \color{cyan}{\text{4 :}} \\ \qquad \begin{array}{ccc} 1 & \color{red}{1} & \color{blue}{1} \\ \color{red}{1} & \color{blue}{1} & \color{green}{1} \\ \color{blue}{1} & \color{green}{1} & \color{cyan}{1} \end{array} \\ \end{array}

Thus it takes 4 hours

Output

FNG3. Grid Spread Timer

2s256 MB

This problem is based on an Amazon interview problem described here.

You are given an $m \times n$ grid where each cell contains either a zombie ( $1$ ) or a human ( $0$ ).

Every hour, all zombies simultaneously infect their adjacent humans. A zombie can infect the human directly up, down, left, or right of it (not diagonally).

Return the number of hours until no humans remain on the grid, or $-1$ if it is impossible (i.e., there are humans but no zombies to infect them).

Constraints

$1 \le m, n \le 500$
Each cell is $0$ or $1$ .

Input

\begin{array}{l} m \quad n \\ g_{0,0} \quad g_{0,1} \quad \cdots \quad g_{0,n-1} \\ \vdots \\ g_{m-1,0} \quad \cdots \quad g_{m-1,n-1} \end{array}

Output

$ans$

Samples

Input

Explanation

\begin{array}{l} \text{After hour } \color{red}{\text{1 :}} \\ \qquad \begin{array}{ccccc} \color{red}{1} & 1 & 1 & \color{red}{1} & 1 \\ \color{red}{1} & 1 & \color{red}{1} & 1 & \color{red}{1} \\ 0 & \color{red}{1} & 0 & \color{red}{1} & 1 \\ \color{red}{1} & 1 & \color{red}{1} & 0 & \color{red}{1} \end{array} \\ \\ \text{After hour } \color{blue}{\text{2 :}} \\ \qquad \begin{array}{ccccc} \color{red}{1} & 1 & 1 & \color{red}{1} & 1 \\ \color{red}{1} & 1 & \color{red}{1} & 1 & \color{red}{1} \\ \color{blue}{1} & \color{red}{1} & \color{blue}{1} & \color{red}{1} & 1 \\ \color{red}{1} & 1 & \color{red}{1} & \color{blue}{1} & \color{red}{1} \end{array} \end{array}

Output

Input

2 2
1 0
0 1

Explanation

\begin{array}{l} \text{After hour } \color{red}{\text{1 :}} \\ \qquad \begin{array}{cc} 1 & \color{red}{1} \\ \color{red}{1} & 1 \end{array} \\ \\ \end{array}

Output

Input

Explanation

\begin{array}{l} \text{After hour } \color{red}{\text{1 :}} \\ \qquad \begin{array}{ccc} 1 & \color{red}{1} & 0 \\ \color{red}{1} & 0 & 0 \\ 0 & 0 & 0 \end{array} \\ \\ \text{After hour } \color{blue}{\text{2 :}} \\ \qquad \begin{array}{ccc} 1 & \color{red}{1} & \color{blue}{1} \\ \color{red}{1} & \color{blue}{1} & 0 \\ \color{blue}{1} & 0 & 0 \end{array} \\ \\ \text{After hour } \color{green}{\text{3 :}} \\ \qquad \begin{array}{ccc} 1 & \color{red}{1} & \color{blue}{1} \\ \color{red}{1} & \color{blue}{1} & \color{green}{1} \\ \color{blue}{1} & \color{green}{1} & 0 \end{array} \\ \\ \text{After hour } \color{cyan}{\text{4 :}} \\ \qquad \begin{array}{ccc} 1 & \color{red}{1} & \color{blue}{1} \\ \color{red}{1} & \color{blue}{1} & \color{green}{1} \\ \color{blue}{1} & \color{green}{1} & \color{cyan}{1} \end{array} \\ \end{array}

Thus it takes 4 hours

Output