Diamond Mine

Time limit0.75sMemory limit128 MB

Summary

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.

Level: Hard8 of 10
Topics: Dynamic programming, Binary search, Geometry, Matrix
Solved: No attempts yet

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.

Examples4

Example 1
Input
```
5 5
01100
01011
11111
01111
11111
```
Expected output
```
3
```
Example 2
Input
```
5 5
01100
00011
11111
01111
11111
```
Expected output
```
2
```
Example 3
Input
```
4 4
0000
0000
0000
0000
```
Expected output
```
0
```
Example 4
Input
```
3 6
111000
101111
111111
```
Expected output
```
2
```