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;

        }