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

$ curl repovive.com/contests/maang/problems/01

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████

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

$ curl repovive.com/contests/maang/problems/01

Repovive

Grid Spread Timer - MAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG01. Grid Spread Timer

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

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

Multiple zombies spread simultaneously. After hour 1, every human adjacent to a zombie is infected. After hour 2, all remaining humans are reached. Answer: 2

Output

Input

2 2
1 0
0 1

Explanation

Zombies at $(0,0)$ and $(1,1)$ each infect the human diagonally opposite them in one hour. Answer: 1

Output

Input

Explanation

Single zombie at the top-left corner $(0,0)$ . The infection spreads outward; the last cell reached is $(2,2)$ at Manhattan distance $2+2=4$ . Answer: 4

Output

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

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

Zombies at $(0,0)$ and $(1,1)$ each infect the human diagonally opposite them in one hour. Answer: 1

Single zombie at the top-left corner $(0,0)$ . The infection spreads outward; the last cell reached is $(2,2)$ at Manhattan distance $2+2=4$ . Answer: 4