作者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/cn.aspx?n=bbs/Marginalman/M.1730201059.A.82F.html