Re: [閒聊] 每日leetcode已回收
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/05/15 02:17)推噓0(0推 0噓 2→)留言2則, 2人參與討論串221/1548 (看更多)
※ 引述《DJYOSHITAKA (franchouchouISBEST)》之銘言：
: 原本想要寫第二題
: 被你版系列文搞到:(
: py好難
: 我一定有一堆地方寫的有問題
: 懶得檢查 對不起
: def dfs(self, i, j, cur, cur_max, grid: List[List[int]]) -> int:
: if self.visit[i][j] == 1 or grid[i][j] == 0:
: return cur
: m = len(grid)
: n = len(grid[0])
: self.visit[i][j] = 1
: cur += grid[i][j]
: if i-1 >= 0:
: cur_max = max(cur_max, self.dfs(i-1, j, cur, cur_max, grid))
: if i+1 < m:
: cur_max = max(cur_max, self.dfs(i+1, j, cur, cur_max, grid))
: if j-1 >= 0:
: cur_max = max(cur_max, self.dfs(i, j-1, cur, cur_max, grid))
: if j+1 < n:
: cur_max = max(cur_max, self.dfs(i, j+1, cur, cur_max, grid))
: self.visit[i][j] = 0
: return cur_max
: def getMaximumGold(self, grid: List[List[int]]) -> int:
: ans = 0
: for i in range(len(grid)):
: for j in range(len(grid[0])):
: self.visit = [[0]*len(grid[0]) for i in range(len(grid))]
: ans = max(ans, self.dfs(i, j, 0, 0, grid))
: return ans
思路:
經典DFS
Python Code:
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
max_res = 0
def dfs(grid,visited,x,y):
visited.add((x,y))
if grid[y][x] == 0:
return 0
else:
res = grid[y][x]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for i in range(4):
new_x = x+dx[i]
new_y = y+dy[i]
if new_x>=0 and new_x<m and new_y>=0 and new_y<n:
if grid[new_y][new_x] !=0 and (new_x,new_y) not in
visited:
res =
max(dfs(grid,visited,new_x,new_y)+grid[y][x],res)
visited.remove((x,y))
return res
for i in range(n):
for j in range(m):
max_res = max(dfs(grid,set(),j,i),max_res)
return max_res
晚安捏
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.138.16 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715710635.A.423.html
→
05/15 02:17,
1年前
, 1F
05/15 02:17, 1F
→
05/15 02:18,
1年前
, 2F
05/15 02:18, 2F
討論串 (同標題文章)