Diamond Mine

Given an R by C grid of 0s and 1s, find the largest size of a diamond shape (a 45-degree rotated square outline) formed entirely of 1s.

Hard8Dynamic programmingBinary searchGeometryMatrixNo attempts yetTime limit0.75sMemory limit128 MB

Description

Examples4

Problem

A diamond mine is an R-row by C-column grid of 0s and 1s.

A diamond is the boundary of a square made of 1s after the square is rotated by 45 degrees. Diamonds of sizes 1, 2, and 3 look like this:

size 1:    size 2:    size 3:
                         1
              1         1 1
   1         1 1       1   1
              1         1 1
                         1

Write a program that finds the size of the largest diamond that can be formed in the grid.

Input

The first line contains R and C. Both R and C are positive integers no greater than 750. Each of the next R lines describes one row of the diamond mine using 0s and 1s.

Output

Print the size of the largest diamond in the mine. If there is no diamond, print 0.