Longest Line of Consecutive One in Matrix
https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/description/
public class Solution {
public int longestLine(int[][] M) {
if(M == null || M.length == 0 || M[0] == null || M.length == 0){
return 0;
}
int m = M.length, n = M[0].length;
int[][][] dp = new int[m][n][4];
int max = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(M[i][j] == 0){
continue;
}
for(int k = 0; k < 4; k++){
dp[i][j][k] = 1;
}
if(inBound(i, j - 1, m, n)){
dp[i][j][0] = dp[i][j - 1][0] + 1;
max = Math.max(max, dp[i][j][0]);
}
if(inBound(i - 1, j - 1, m, n)){
dp[i][j][1] = dp[i - 1][j - 1][1] + 1;
max = Math.max(max, dp[i][j][1]);
}
if(inBound(i - 1, j, m, n)){
dp[i][j][2] = dp[i - 1][j][2] + 1;
max = Math.max(max, dp[i][j][2]);
}
if(inBound(i - 1, j + 1, m, n)){
dp[i][j][3] = dp[i - 1][j + 1][3] + 1;
max = Math.max(max, dp[i][j][3]);
}
max = Math.max(max, 1);
}
}
return max;
}
private boolean inBound(int i , int j, int m, int n){
return i >= 0 && i < m && j >= 0 && j < n;
}
}