Problem statement

https://leetcode.com/problems/path-with-maximum-gold/

Solution

We can use backtracking here. Or we can use bitmask here

Complexity

It is O(2^k*m*n) for time and space, where k is number of places with gold.

Code

class Solution:
    def getMaximumGold(self, M):
        n, m = len(M), len(M[0])
        coins = [(i, j) for i, j in product(range(n), range(m)) if M[i][j]]
        d = {(x, y): i for i, (x, y) in enumerate(coins)}
        G = defaultdict(list)
        for x, y in product(range(n), range(m)):
            for i, j in [[x + 1, y], [x - 1, y], [x, y - 1], [x, y + 1]]:
                if not 0 <= i < n or not 0 <= j < m or M[i][j] == 0: continue
                G[(x, y)] += [(i, j)]

        @lru_cache(None)
        def dp(mask, x, y):
            ans = M[x][y]
            mask2 = mask ^ (1 << d[x, y])
            for i, j in G[x, y]:
                if mask >> d[i, j] & 1 == 1: continue
                ans = max(ans, M[x][y] + dp(mask2, i, j))
            return ans
        
        if not coins: return 0
        return max(dp(0, x, y) for x, y in coins)