Re: [閒聊] 每日leetcode已回收
https://leetcode.com/problems/path-with-maximum-gold/description
1219. Path with Maximum Gold
給你一個二維陣列grid表示金礦的座標，grid[i][j] 表示該位置有多少金礦，你可以
從任意位置當起點開始挖金礦，滿足以下條件：
1.每次都要挖完當前位置的金礦
2.你可以往上下左右移動
3.你不可以移動到沒金礦的位置
求出最多可以挖多少金礦
思路：
1.從每個金礦座標開始窮舉所有挖金礦的可能，用回朔法標記已經挖過的金礦，取最大
的即可。
py code:
-------------------------------------
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def dfs(y: int, x: int):
if y < 0 or y == m or x < 0 or x == n or grid[y][x] == 0:
return 0
tmp = grid[y][x]
grid[y][x] = 0
profit = tmp + max(dfs(y + 1, x), dfs(y - 1, x), dfs(y, x + 1),
dfs(y, x - 1))
grid[y][x] = tmp
return profit
res = 0
for i in range(m):
for j in range(n):
res = max(res, dfs(i, j))
return res
-------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.139.139.57 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715650295.A.26A.html
推
05/14 09:33,
1年前
, 1F
05/14 09:33, 1F
推
05/14 09:34,
1年前
, 2F
05/14 09:34, 2F
推
05/14 09:37,
1年前
, 3F
05/14 09:37, 3F
→
05/14 09:38,
1年前
, 4F
05/14 09:38, 4F
推
05/14 09:40,
1年前
, 5F
05/14 09:40, 5F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 217 之 1554 篇)：