https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/
用 prev 來記錄前一個 column 的第 i 格是否能夠走到，cur 來記錄目前 column 的第 i 格是否能夠走到。
在 grid[i][j] 的時候，檢查 grid[i - 1][j - 1], grid[i][j - 1], grid[i + 1][j - 1] 是否小於 grid[i][j]，並且還要同時滿足對應的 prev[i - 1], prev[i], prev[i + 1] 爲 true。
如果在跑過 jth column 後沒有任何爲 true，那麼代表沒辦法再繼續走下去了，可以回傳結果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| int maxMoves(vector<vector<int>>& grid) {
int steps = 0;
int cols = grid[0].size();
int rows = grid.size();
vector<bool> prev(rows, true);
for (int j = 1; j < cols; j++){
vector<bool> cur(rows, false);
bool stop = true;
for (int i = 0; i < rows; i++){
for (int k = max(0, i - 1); k <= min(i + 1, rows - 1); k++){
if (prev[k] && grid[k][j - 1] < grid[i][j]){
cur[i] = true;
stop = false;
}
}
}
swap(prev, cur);
if (stop){
return steps;
}
else {
steps++;
}
}
return steps;
}
|
time complexity: $O(rows \times cols)$
space complextiy: $O(rows)$
當然也可以用 dfs + dp 來解這一題。
dfs(row, col) 會回傳「從 grid[row][col] 開始走，能走幾步」。
注意當 col == cols - 1 時要回傳 0，因爲已經抵達右邊的邊界，沒辦法繼續走下去。
這個方法時間複雜度會跟上面一樣，因爲每一個 dfs(row, col) 都只會算過一次，算過之後就會存在 dp[row][col] 裡面。但是空間複雜度會比較大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| int maxMoves(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
vector<vector<int>> dp(rows, vector<int> (cols, -1));
function<int(int, int)> dfs = [&](int row, int col){
if (col >= cols - 1){
return 0;
}
if (dp[row][col] != -1){
return dp[row][col];
}
int steps = 0;
for (int r = max(row - 1, 0); r <= min(row + 1, rows - 1); r++){
if (grid[row][col] < grid[r][col + 1]){
steps = max(steps, 1 + dfs(r, col + 1));
}
}
dp[row][col] = steps;
return steps;
};
int ans = 0;
for (int r = 0; r < rows; r++){
ans = max(ans, dfs(r, 0));
}
return ans;
}
|
time complexity: $O(rows \times cols)$
space complextiy: $O(rows \times cols)$