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

Alexander Grey on Unsplash

題目敘述

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

從任何一個有金礦的格子點出發，以四聯通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{向北、向東、向西、向南探索 可拿到的金礦}

Reference

[1] Path with Maximum Gold - LeetCode