1219. Path with Maximum Gold - Explanation

class Solution:
    def getMaximumGold(self, grid: list[list[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r, c, visit):
            if min(r, c) < 0 or r == ROWS or c == COLS or grid[r][c] == 0 or (r, c) in visit:
                return 0

            visit.add((r, c))
            res = grid[r][c]

            for dr, dc in directions:
                res = max(res, grid[r][c] + dfs(r + dr, c + dc, visit))

            visit.remove((r, c))
            return res

        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] != 0:
                    res = max(res, dfs(r, c, set()))
        return res

class Solution:
    def getMaximumGold(self, grid: list[list[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r, c):
            if min(r, c) < 0 or r == ROWS or c == COLS or grid[r][c] == 0:
                return 0

            gold = grid[r][c]
            grid[r][c] = 0
            res = 0

            for dr, dc in directions:
                res = max(res, dfs(r + dr, c + dc))

            grid[r][c] = gold
            return gold + res

        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] != 0:
                    res = max(res, dfs(r, c))
        return res

class Solution:
    def getMaximumGold(self, grid: list[list[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [1, 0, -1, 0, 1]
        index = [[0] * COLS for _ in range(ROWS)]
        idx = 0

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] != 0:
                    index[r][c] = idx
                    idx += 1

        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] > 0:
                    q = deque([(r, c, grid[r][c], 1 << index[r][c])])
                    while q:
                        row, col, gold, mask = q.popleft()
                        res = max(res, gold)

                        for i in range(4):
                            nr, nc = row + directions[i], col + directions[i + 1]
                            if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] > 0:
                                idx = index[nr][nc]
                                if not (mask & (1 << idx)):
                                    q.append((nr, nc, gold + grid[nr][nc], mask | (1 << idx)))

        return res