作者dont (dont)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Tue Oct 29 19:24:16 2024
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://webptt.com/m.aspx?n=bbs/Marginalman/M.1730201059.A.82F.html