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.
Example:
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.
题目标签：Array
这道题目给了我们一个2d array，让我们找出最长1的长度。这里可以有四个方向，横向，纵向，还有两个不同方向的 斜线。
一开始想到的是维护一个dp 2d array，如果遍历2d array的话，对于rows 是从上到下，对于 每一个row 是从左到右。所以每一个cell的累加方向只能有4个可能：
1. 从左边的cell 累加；
2. 从左上方的cell 累加；
3. 从上方的cell 累加；
4. 从右上方的cell 累加。
但是这里存在一个问题，因为有4个方向的累加，在之后的累加里，会搞不清楚之前存在的值，是从哪个方向累加来的。所以对于每一个cell，我们要把4个方向分开存放。
这样的话，我们可以设一个dp 3d array 在最后一个维度的array里，存放4种不同方向的累加。
比如：最后一个维度 array [1, 2, 3, 4] 每一个value 都代表着对应方向的累加。[左边，左上，上方，右上]。
有了这样的结构，在遍历中，我们就可以累加4个方向的长度，每次遇到M 里是1的cell， 就把 3d array里的4个方向值都设为1，再检查这个cell 的 4个方向，左边，左上，上方，右上，进行累加。在累加完毕后，更新最大的长度。
Java Solution:
Runtime beats 66.48%
完成日期：10/05/2017
关键词：Array, Dynamic Programming
关键点：维护一个3d array，累加4个不同方向的长度
class Solution
{
public int longestLine(int[][] M)
{
if(M == null || M.length == 0)
return 0; int n = M.length;
int m = M[0].length; int[][][] arr = new int[n][m][4];
int longestLine = 0; for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(M[i][j] == 0) // skip 0
continue; // if find a 1, put 1 into 4 cells since this number is 1
for(int k=0; k<4; k++)
arr[i][j][k] = 1;
// then, add its 4 direction left, up-left, up, up-right value into this 4 cells
if(j-1 >= 0)
arr[i][j][0] += arr[i][j-1][0]; // horizontal
if(j-1 >= 0 && i-1 >= 0)
arr[i][j][1] += arr[i-1][j-1][1]; // diagonal
if(i-1 >= 0)
arr[i][j][2] += arr[i-1][j][2]; // vertical
if(j+1 < m && i-1 >= 0)
arr[i][j][3] += arr[i-1][j+1][3]; // anti-diagonal int temp = Math.max(Math.max(arr[i][j][0], arr[i][j][1]), Math.max(arr[i][j][2], arr[i][j][3]));
longestLine = Math.max(longestLine, temp);
}
} return longestLine;
}
}
参考资料：
https://discuss.leetcode.com/topic/87197/java-o-nm-time-dp-solution
LeetCode 题目列表 - LeetCode Questions List