# 0562. Longest Line of Consecutive One in Matrix
###### tags: `Leetcode` `Medium` `Dynamic Programming` `DFS`
Link: https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/
## 思路
dfs 也可以用dp做(官方解答)
拿到一个是1的位置我们就会往四个方向遍历
但要注意的是每一个1我们需要判断它是不是当前这个方向的“头”
例如当前方向是```(1,0)``` 如果```(i-1, j)```已经是1了，那说明当前的```(i,j)```已经不是头了，也就是在算```(i-1,j)```开始的序列的时候肯定已经把```(i-1,j)```算进去了 所以我们不需要再计算从```(i,j)```开始方向为```(1,0)```的dfs了
## Code

class Solution {
    public int longestLine(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m][n];
        int ans = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(mat[i][j]==0) continue;
                
                if(i==0 || (i!=0 && mat[i-1][j]==0)){
                    ans = Math.max(ans, dfs(mat, i, j, 1, 0));
                }
                if(j==0 || (j!=0 && mat[i][j-1]==0)){
                    ans = Math.max(ans, dfs(mat, i, j, 0, 1));
                }
                if((i==0 || j==0) ||(i!=0 && j!=0 && mat[i-1][j-1]==0)){
                    ans = Math.max(ans, dfs(mat, i, j, 1, 1));
                }
                if((i==0 || j==n-1) || (i!=0 && j!=n-1 && mat[i-1][j+1]==0)){
                    ans = Math.max(ans, dfs(mat, i, j, 1, -1));
                }
            }
        }
        return ans;
    }
    private int dfs(int[][] mat, int x, int y, int dirx, int diry){
        int m = mat.length, n = mat[0].length;
        int len = 0;
        while(x>=0 && x<m && y>=0 && y<n && mat[x][y]==1){
            len++;
            x+=dirx;
            y+=diry;
        }
        return len;
    }
}