Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.
Input: [[0,1,1,0], [0,1,1,0], [0,0,0,1]] Output: 3
Hint: The number of elements in the given matrix will not exceed 10,000.
Hint 1One solution is to count ones in each direction separately and find the longest line. Don't you think it will take too much lines of code?
Hint 2Is it possible to use some extra space to make the solution simple?
Hint 3Can we use dynamic programming to make use of intermediate results?
Hint 4Think of a 3D array which can be used to store the longest line obtained so far for each direction.
There is no documentation for this package.