推 JIWP: 大師 05/14 09:33
推 Che31128: 大師 05/14 09:34
推 argorok: 大師 05/14 09:37
→ SecondRun: 大師 05/14 09:38
推 wu10200512: 大師 05/14 09:40
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