🔗 🟡 1219. Path with Maximum Gold 1663

tags: `Weekly Contest 157` `回溯(Backtracking)`

題意

給定一個大小為 $m \times n$ 的網格 $grid$ ，其中 $grid[i][j]$ 表示第 $i$ 行第 $j$ 列的格子中的黃金數量，若該格子布存在黃金則為 $0$ 。

開採必須從任何一個 有黃金 的格子開始，收集該格子中的所有黃金，然後從當前位置向上下左右四個方向移動到其他有黃金的位置。繼續進行相同的選擇，直到無法繼續移動。也就是說，開採路徑上的每個格子都必須 有黃金 。

返回能夠收集的最大黃金數量。

限制條件：

$1 \leq grid.length, grid[i].length \leq 15$
$0 \leq grid[i][j] \leq 100$
有黃金的格子數目不超過 $25$ 。

思路：回溯(Backtracking)

首先確定主要思路：對於每個有黃金的格子，進行深度優先搜索(DFS) ，取走黃金後，再向上下左右四個方向進行搜索。但由於可能存在多個可能的路徑，且彼此之間可能有重疊，因此需要使用 回溯(Backtracking) 法來解決。

由於已經走過的格子不能再走，因此需要將當前格子標記為已訪問，但本來就不能走沒有黃金的格子，因此在取走黃金後，可以先備份當前格子的黃金數量 $origin$ ，再將 $grid[x][y]$ 標記為 $0$ ，就可以表示已訪問，然後向上下左右四個方向進行搜索，並在搜索完畢後將當前格子的黃金數量恢復，以便進行下一次搜索。

複雜度分析

時間複雜度： $O(mn + \min(mn,T) \cdot 3^{\min(mn,T)})$ ，其中 $m$ 和 $n$ 分別表示網格橫列(row)數直行(col)數， $T=25$ 表示最多包含黃金的單元格數量。枚舉起點需要 $O(mn)$ 的時間，可以成為起點的位置必須有黃金，那麼可能的起點有 $\min(mn,T)$ 個。對於每一個起點，第一步最多有 $4$ 個可行的方向，由於不能走已經走過的格子，後面的每一步最多有 $3$ 個可行的方向，因此一次搜索需要的時間約為 $O(4 \times 3^{\min(mn,T) - 2}) = O(3^{\min(mn,T)})$ 。
空間複雜度： $O(\min(mn,T))$ ，遞迴(Recursion)需要的堆疊(Stack)空間。

以上為參考官方解答的粗略分析，更詳細的為甚麼不會超時的分析可以參考這篇文章。

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(x, y):
            res = 0
            origin = grid[x][y] # backup
            grid[x][y] = 0 # mark as visited
            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != 0:
                    res = max(res, dfs(nx, ny))
            grid[x][y] = origin # backtracking
            return res + origin
        
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 0:
                    ans = max(ans, dfs(i, j))
        return ans

class Solution {
public:
    int m, n;
    int DIR[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int dfs(vector<vector<int>>& grid, int x, int y) {
        int res = 0;
        int origin = grid[x][y]; // backup
        grid[x][y] = 0; // mark as visited
        for (int k = 0; k < 4; k++) {
            int nx = x + DIR[k][0], ny = y + DIR[k][1];
            if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] != 0) {
                res = max(res, dfs(grid, nx, ny));
            }
        }
        grid[x][y] = origin; // backtracking
        return res + origin;
    }
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    ans = max(ans, dfs(grid, i, j));
                }
            }
        }
        return ans;
    }
};