Re: [閒聊] 每日leetcode
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
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.25 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1730201059.A.82F.html
討論串 (同標題文章)
完整討論串 (本文為第 1059 之 1550 篇)：