2684. Maximum Number of Moves in a Grid
## 思路
解法1. 直接照題目做DFS
解法2. 因為每次move都是往c+1移動
直接for loop檢查並記錄下一步可以到的row set
如果沒有就回傳目前的col index
## Code
DFS
```python
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
len_r, len_c = len(grid), len(grid[0])
@cache
def recur(r, c):
max_moves = 0
for nr, nc in (r-1, c+1), (r, c+1), (r+1, c+1):
if 0 <= nr < len_r and 0 <= nc < len_c and grid[r][c] <
grid[nr][nc]:
max_moves = max(max_moves, 1 + recur(nr, nc))
return max_moves
res = 0
for r in range(len_r):
res = max(res, recur(r, 0))
return res
```
```python
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
len_r, len_c = len(grid), len(grid[0])
curr_r = {r for r in range(len_r)}
for c in range(len_c-1):
next_r = set()
for r in curr_r:
for nr in (r-1, r, r+1):
if 0 <= nr < len_r and grid[nr][c+1] > grid[r][c]:
next_r.add(nr)
if not next_r:
return c
curr_r = next_r
return len_c-1
```