2024-05-14|閱讀時間 ‧ 約 25 分鐘

尋寶之旅 挖掘最多金礦的走法 (DFS+最佳化)Leetcode #1219

題目敘述

題目給定一個二維的整數陣列,每個格子點裡面的數字代表金礦的多寡。

從任何一個有金礦的格子點出發,以四聯通N4的方式向探索周圍的格子點,每個格子點只能拜訪一次,不能重複拜訪

請問最多能挖到多少金礦


原本的英文題目敘述


測試範例

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
[5,8,7],
[0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.ㄖㄨˉ

約束條件

Constraints:

  • m == grid.length

m代表地圖的高

  • n == grid[i].length

n代表地圖的寬

  • 1 <= m, n <= 15

地圖的高m 和 地圖的寬n都介於1 ~ 15之間。

  • 0 <= grid[i][j] <= 100

每個格子點蘊藏的金礦介於0~100單位之間。

  • There are at most 25 cells containing gold.

最多有25個格子點蘊藏金礦。


演算法 DFS模擬N4走法

從題意出發,每個格子點可以向東、南、西、北四個方向探索,而且不可以重複拜訪

相當於

最多金礦挖掘數

= 當下格子點的金礦數量 +Max{ 從N4挑一條路徑,拜訪可拿到的金礦}

= 當下格子點的金礦數量 + Max{向北、向東、向西、向南探索 可拿到的金礦}


使用DFS模擬N4走法,配合最大值的選擇策略最佳化即可。


程式碼 DFS模擬N4走法

class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:

h, w = len(grid), len(grid[0])

def dfs(r,c):

## Base case
# Out-of-boundary or visited or no score
if not ( 0 <= r < h) or not ( 0 <= c < w ) or grid[r][c] <= 0:
return 0

## General cases
# Go on maximal score path in N4
cur = grid[r][c]

# mark as visited to avoid repeated traversal
grid[r][c] = - cur

# Select path with maximal score in N4
res = cur + max(dfs(r+1, c), dfs(r-1, c), dfs(r, c+1), dfs(r, c-1))

# restore origin state
grid[r][c] *= -1
return res

# ----------------------------
best = 0

# 2D board scan
for r in range(h):
for c in range(w):
if grid[r][c] > 0:
best = max(best, dfs(r,c))

return best

複雜度分析

時間複雜度: O(h*w + k*4^k)

需要一個2D掃描,掃描每個格子點恰好掃描一次。

最多有k個含有金礦的格子點,每次可探索四個相鄰的鄰居格子點,
探索路徑狀態最多為O(k*4^k)


空間複雜度: O(k)

探索深度最深為O(k),就是把可能相鄰的k個含有金礦的格子點都走過一遍。


關鍵知識點

從題意出發,每個格子點可以向東、南、西、北N4四個方向探索,
而且不可以重複拜訪

相當於

最多金礦挖掘數

= 當下格子點的金礦數量 +Max{ 從N4挑一條路徑,拜訪可拿到的金礦}

= 當下格子點的金礦數量 + Max{向北、向東、向西、向南探索 可拿到的金礦}


Reference

[1] Path with Maximum Gold - LeetCode

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

作者的相關文章

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.