LeetCode [562] Longest Line of Consecutive One in Matrix

 562. Longest Line of Consecutive One in Matrix

Medium

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public int longestLine(int[][] M) { int m = M.length; if(m==0) return 0; int n = M[0].length; if(n==0) return 0; int[][][] dp = new int[m][n][4];//h, v, f, b int max = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(M[i][j]==1){ int h, v, f, b; //horizontal if(j==0) dp[i][j][0] = 1; else dp[i][j][0] = dp[i][j-1][0]+1; //vertical if(i==0) dp[i][j][1] = 1; else dp[i][j][1] = dp[i-1][j][1]+1; //forward if(i==0 || j==n-1) dp[i][j][2] = 1; else dp[i][j][2] = dp[i-1][j+1][2] + 1; //backward if(i==0 || j==0) dp[i][j][3] = 1; else dp[i][j][3] = dp[i-1][j-1][3] + 1; max = Math.max(max, dp[i][j][0]); max = Math.max(max, dp[i][j][1]); max = Math.max(max, dp[i][j][2]); max = Math.max(max, dp[i][j][3]); } } } return max; } }