Longest Line of Consecutive One

第一种方法是直接做搜索，LC现在感觉大数据的test case少了，所以繁琐一点也是能过的.
对于每一个点，朝8个方向进行搜索 （其实朝前向的四个方向就可以） 同时将扫过的点记录下来，以便不往回找.

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;
    }
};