50120. Consecutive 1's

I'm a slow walker, but I never walk backwards.

Task Description

We have a two-dimensional $N×N$ array. Each element of the array is either $0$ or $1$. Write a program to compute the length of the longest consecutive “$1$”'s in a row, in a column, or in a diagonal direction. You only need to consider the diagonal direction as going from $(x, y)$ to $(x+1, y+1)$, as in the following figure.

samplesample

The following figure has three examples.

samplesample

Input Format

The first line has the integer $N$, the size of the array. The next $N$ lines have $N$ integers, which are either $1$ or $0$. They are the elements of the array.

  • $0 \lt N \lt 1000$

Output Format

The output has only one integer -- the length of the longest consecutive $1$'s in a row, in a column, or in the diagonal direction.

Subtask

  • 50 points: Compute the length of the longest continuous $1$'s in a row or in a column. You can safely ignore the diagonal direction.
  • 50 points: Compute the length of the longest continuous $1$'s in a row, in a column, or in the diagonal direction.

Sample Input 1

5
1 0 1 1 0
1 0 0 0 1
0 1 1 1 1
0 1 0 0 1
0 0 0 1 0

Sample Output 1

4

Sample Input 2

5
1 0 1 1 0
1 0 0 0 1
1 0 1 1 0
0 1 0 0 1
0 0 0 0 1

Sample Output 2

3

Sample Input 3

5
0 0 1 1 0
0 0 0 0 1
1 1 0 1 0
0 1 1 0 1
0 0 0 1 1

Sample Output 3

3

Hint

You need to get the answer by exmaining the data only once. That is, if you are looking for the answer in a row, you need to scan the row once and get the answer. You cannot try every element as a possible starting point of the longest sequence of 1's, because you will get TLE.

Discussion