#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Grid Spread Timer - FAANG Problems | Repovive

FAANG3. 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

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).

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

\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}

$ans$

\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}

\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}

\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