> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/562.-longest-line-of-consecutive-one-in-matrix-3d-dp.md).

# 562. Longest Line of Consecutive One in Matrix (3D DP)

## brute force: 

T: O(mn)

S: O(1)

針對四種 case 去寫, 但 code 會太長, 

有效計算對角線的座標:

<https://www.cnblogs.com/grandyang/p/6900866.html>

## 3-D DP

T: O(mn)

S: O(4mn)

```java
class Solution {
    public int longestLine(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][][] dp = new int[m][n][4];
        
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) { // not 1
                    continue;
                }
                for (int k = 0; k < 4; k++) { // if 1, give dp[i][j] plus 1
                    dp[i][j][k] = 1;
                }
                if (j-1 >= 0) {
                    dp[i][j][0] += dp[i][j-1][0]; // horizon
                }
                if (i-1 >= 0) {
                    dp[i][j][1] += dp[i-1][j][1]; // vertical
                }
                if (i-1 >= 0 && j-1 >= 0) {
                    dp[i][j][2] += dp[i-1][j-1][2]; // diagno
                }
                if (i-1 >= 0 && j+1 < n) {
                    dp[i][j][3] += dp[i-1][j+1][3]; // anti-diagno
                }
                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;
    }
}
```