562. Longest Line of Consecutive One in Matrix

发表于 | 分类于

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：DP, O(nm)

用一个三维数组记录每一个格子上4个方向的最长的个数。同时更新一下最长的值即可。
C++

1

Java

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
41
42
43
44
45
46
47
48
49
50
51
public class Solution {
    public int longestLine(int[][] M) {
        if (M.length == 0 || M[0].length == 0) {
            return 0;
        }
        int[][][] dp = new int[M.length][M[0].length][4];
        if (M[0][0] == 1) {
            for (int i = 0; i < 4; i++) {
                dp[0][0][i] = 1;
            }
        }
        int res = 0;
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M[0].length; j++) {
                if (M[i][j] == 0) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    dp[i][j][k] = 1;
                }
                // vertical line
                if (i > 0) {
                    dp[i][j][0] = dp[i - 1][j][0] + 1;
                }
                // horizontal line
                if (j > 0) {
                    dp[i][j][1] = dp[i][j - 1][1] + 1;
                }
                // diagonal line
                if (i > 0 && j < M[0].length - 1) {
                    dp[i][j][3] = dp[i - 1][j + 1][3] + 1;
                }
                // anti diagonal line
                if (i > 0 && j > 0) {
                    dp[i][j][2] = dp[i - 1][j - 1][2] + 1;
                }
                res = Math.max(res, Math.max(dp[i][j][0], dp[i][j][1]));
                res = Math.max(res, Math.max(dp[i][j][2], dp[i][j][3]));
            }
        }
        return res;
    }
}