| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem E
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 |