# Longest Line of Consecutive One in Matrix

第一种方法是直接做搜索，LC现在感觉大数据的test case少了，所以繁琐一点也是能过的.

对于每一个点，朝8个方向进行搜索 （其实朝前向的四个方向就可以） 同时将扫过的点记录下来，以便不往回找.

**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.

给定01矩阵M，计算矩阵中一条线上连续1的最大长度。一条线可以为横向、纵向、主对角线、反对角线。

**提示：**

给定矩阵元素个数不超过10,000

```
class Solution {
public:

    bool isValid(int x, int y, vector<vector<int>>& M, vector<vector<bool>> &visited){
        if(x >= 0 && x < M.size() && y >= 0 && y < M[0].size() && M[x][y] == 1 && !visited[x][y]){
            return true;
        }

        return false;
    }

    int longestLine(vector<vector<int>>& M) {
        if(M.empty() || M[0].empty()){
            return 0;
        }

        int row = M.size(), col = M[0].size();
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        vector<pair<int, int>> directions = {{1, 0}, {0, 1}, {1, 1}, {-1, 1}};
        int max_len = 0;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(M[i][j] == 0){
                    continue;
                }

                for(auto it : directions){
                    int cur_x = i, cur_y = j, cur_len = 1;
                    while(isValid(cur_x + it.first, cur_y + it.second, M, visited)){
                        cur_x += it.first;
                        cur_y += it.second;
                        cur_len += 1;
                    }

                    max_len = max(max_len, cur_len);
                }
            }
        }

        return max_len;
    }
};
```

参照网上，第二种方法是dp，这个dp是要建立三维数组，不仅仅是行列这两维，第三维有代表的是连续1的四个方向 (前后，上下，斜，反斜). 做法也很直接.

```
class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        if(M.empty() || M[0].empty()) return 0;
        int row = M.size(), col = M[0].size();
        vector<vector<vector<int>>> dp(row+1, vector<vector<int>>(col+1, vector<int>(4, 0)));
        int max_len = 0;
        for(int i=1; i<=row; i++){
            for(int j=1; j<=col; j++){
                if(M[i-1][j-1] == 0) continue;
                dp[i][j][0] = dp[i-1][j][0] + 1;
                dp[i][j][1] = dp[i][j-1][1] + 1;
                dp[i][j][2] = dp[i-1][j-1][2] + 1;
                if(j != col) dp[i][j][3] = dp[i-1][j+1][3] + 1;
                for(int k=0; k<4; k++){
                    max_len = max(max_len, dp[i][j][k]);
                }

            }
        }
        return max_len;
    }
};

## Blog link: https://code.dennyzhang.com/longest-line-of-consecutive-one-in-matrix
## Basic Ideas:
##
##   dp(i, j): 
##        horizontal:    dp(i, j-1)
##        vertical:      dp(i-1, j)
##        diagonal:      dp(i-1, j-1)
##        anti-diagonal: dp(i-1, j+1)
##
## Complexity: Time O(m*n), Space O(m*n)


class Solution:
    def longestLine(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        row_count = len(M)
        if row_count == 0: return 0
        col_count = len(M[0])

        dp = [[[0, 0, 0, 0] for j in range(col_count)] for i in range(row_count)]
        max_count = 0
        # dynamic programming
        for i in range(row_count):
            for j in range(col_count):
                if M[i][j] == 0: continue
                dp[i][j] = [1, 1, 1, 1]
                if j>0: dp[i][j][0] = dp[i][j-1][0] + 1
                if i>0: dp[i][j][1] = dp[i-1][j][1] + 1
                if i>0 and j>0: dp[i][j][2] = dp[i-1][j-1][2] + 1
                if i>0 and j<col_count-1: dp[i][j][3] = dp[i-1][j+1][3] + 1
                max_count = max(max_count, max(dp[i][j]))
        return max_count





class Solution {
    public int longestLine(int[][] M) {
        int n = M.length, max = 0;
        if (n == 0) return max;
        int m = M[0].length;
        int[][][] dp = new int[n][m][4];
        for (int i=0;i<n;i++) 
            for (int j=0;j<m;j++) {
                if (M[i][j] == 0) continue;
                for (int k = 0;k < 4;k++) dp[i][j][k] = 1;
                if (j > 0) dp[i][j][0] += dp[i][j-1][0]; // horizontal line
                if (j > 0 && i > 0) dp[i][j][1] += dp[i-1][j-1][1]; // anti-diagonal line
                if (i > 0) dp[i][j][2] += dp[i-1][j][2]; // vertical line
                if (j < m-1 && i > 0) dp[i][j][3] += dp[i-1][j+1][3]; // diagonal line
                max = Math.max(max, Math.max(dp[i][j][0], dp[i][j][1]));
                max = Math.max(max, Math.max(dp[i][j][2], dp[i][j][3]));
            }
        return max;
    }
}






 public int longestLine(int[][] matrix)
        {
            int m = matrix.Length;
            int n = matrix[0].Length;
            int ans = 0;

            int[][][] F = new int[m][][];
            for(int i = 0; i < m; i++)
            {
                F[i] = new int[n][];
                for(int j = 0; j < n; j++)
                {
                    F[i][j] = new int[4];
                }
            }

            for(int i = 0; i < m; i++)
            {
                for(int j= 0; j < n; j++)
                {
                    if(matrix[i][j] == 0)
                    {
                        continue;
                    }

                    for (int k = 0; k < 4; k++)
                    {
                        F[i][j][k] = 1;
                    }

                    if (j > 0)
                    {
                        F[i][j][0] = F[i][j - 1][0] + 1;
                    }

                    if(i > 0)
                    {
                        F[i][j][1] = F[i - 1][j][1] + 1;
                    }

                    if (i > 0 && j > 0)
                    {
                        F[i][j][2] = F[i - 1][j- 1][2] + 1;
                    }

                    if(i > 0 && j < n - 1)
                    {
                        F[i][j][3] = F[i - 1][j + 1][3] + 1;
                    }

                    for (int k = 0; k < 4; k++)
                    {
                        ans = Math.Max(ans, F[i][j][k]);
                    }

                }
            }

            return ans;

        }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://liuxue2010.gitbook.io/data-structure-and-algorithms/dynamic-programming-i/longest-line-of-consecutive-one-in-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.