Under construction

Still being built. Things may change

Baby Shark 2

Interview

Time limit2sMemory limit512 MB

Summary
Given an N by M grid with some cells holding sharks, find the empty cell whose Chebyshev distance to the nearest shark is largest.
Level

Medium4 of 10

Topics
BFS, Graph, Brute force, Implementation
Solved
No attempts yet

Problem

In a space of size N×MN \times M there are several baby sharks. The space is divided into square cells of size 1×11 \times 1. Each cell contains at most one baby shark.

The safety distance of a cell is the distance from that cell to the nearest baby shark. The distance between two cells is the number of cells that must be passed through to get from one cell to the other, and movement is possible in the 8 adjacent directions (including diagonals).

Find the cell with the greatest safety distance.

Input

The first line gives the size of the space, NN and MM (2≤N,M≤502 \le N, M \le 50). From the second line, NN lines give the state of the space, where 0 is an empty cell and 1 is a cell containing a baby shark. Only inputs with at least one empty cell and at least one shark are given.

Output

Print the maximum safety distance on the first line.

Examples2

  1. Example 1

    Input
    5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1
    Expected output
    2

  2. Example 2

    Input
    7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1
    Expected output
    2