第一種方法是直接做搜索汞幢，LC現(xiàn)在感覺(jué)大數(shù)據(jù)的test case少了，所以繁瑣一點(diǎn)也是能過(guò)的.
對(duì)于每一個(gè)點(diǎn)眼溶，朝8個(gè)方向進(jìn)行搜索 （其實(shí)朝前向的四個(gè)方向就可以） 同時(shí)將掃過(guò)的點(diǎn)記錄下來(lái)授药，以便不往回找.

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

參照網(wǎng)上，第二種方法是dp凹嘲，這個(gè)dp是要建立三維數(shù)組师倔，不僅僅是行列這兩維，第三維有代表的是連續(xù)1的四個(gè)方向 (前后，上下趋艘，斜疲恢，反斜). 做法也很直接.

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