題目敘述
題目給定一個二維的整數陣列，每個格子點裡面的數字代表金礦的多寡。
從任何一個有金礦的格子點出發，以四聯通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(ｈ＊ｗ + k*4^k)
需要一個２Ｄ掃描，掃描每個格子點恰好掃描一次。
最多有k個含有金礦的格子點，每次可探索四個相鄰的鄰居格子點，
探索路徑狀態最多為O(k*4^k)
空間複雜度: O(k)
探索深度最深為O(k)，就是把可能相鄰的k個含有金礦的格子點都走過一遍。
關鍵知識點
從題意出發，每個格子點可以向東、南、西、北N4四個方向探索，
而且不可以重複拜訪。
相當於
最多金礦挖掘數
= 當下格子點的金礦數量 +Max{ 從N4挑一條路徑，拜訪可拿到的金礦}
= 當下格子點的金礦數量 + Max{向北、向東、向西、向南探索 可拿到的金礦}
