第一種方法是直接做搜索汞幢,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;
}
};