[Login|Register]
Problems

Status

Rank

Problem 1264
Longest ā€˜Vā€™ sequence
Time Limit: 1000ms
Memory Limit: 65536kb
Description
There is an N *M matrix with its element 0 or 1. Now we want to compute the length of longest consecutive sequence of 1 which looks like 'V'. If the current coordinate is (x, y), then it is consecutive with coordinate(x+1, y+1) or coordinate(x-1, y+1).
For example, look at the 3 by 3 matrix below.
1 1 0
1 1 1
1 1 0
So coordinate(2, 1)→coordinate(3, 2)→coordinate(2, 3) is a legal 'V' shape sequence. What`s more, it is the longest one.
Input
The first line, an integer T, representing T test cases below. (T<=10).
For each test case, the first line contains two integers N, M (1<=N, M<=1000), followed by an N by M matrix with its element 0 or 1.
Output
For each case, output the length of longest consecutive sequence of 1 which looks like 'V'. If such sequence cannot be found, output -1 instead.
Sample Input
3
2 2
1 0
0 1

3 3
1 1 0
1 1 1
1 1 0

3 4
1 1 1 0
1 1 0 1
1 0 1 0
Sample Output
-1
3
4
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.3ms with 1 query(s).