Problem statement

https://binarysearch.com/problems/Collecting-Coins-Sequel/

Solution

Equal to Leetcode 1219. Path with Maximum Gold.

Complexity

It is O(2^k * m * n) for time and space.

Code

class Solution:
    def solve(self, M):
        n, m = len(M), len(M[0])
        coins = [i*m + j for i, j in product(range(n), range(m)) if M[i][j]]
        d = {x: i for i, x 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*m + y] += [i*m + j]

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