1219. 黄金矿工

from itertools import product
from typing import List, Set, Tuple


class Solution:
    def get_maximum_gold_from(self, grid: List[List[int]], visited: Set[Tuple[int, int]], i: int, j: int) -> int:
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        if n == 0:
            return 0

        if not (0 <= i < m and 0 <= j < n):
            return 0

        if (i, j) in visited or grid[i][j] == 0:
            return 0

        visited.add((i, j))
        extra = max(
            self.get_maximum_gold_from(grid, visited, i + 1, j),
            self.get_maximum_gold_from(grid, visited, i - 1, j),
            self.get_maximum_gold_from(grid, visited, i, j + 1),
            self.get_maximum_gold_from(grid, visited, i, j - 1)
        )
        visited.remove((i, j))

        return extra + grid[i][j]

    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        if n == 0:
            return 0

        return max(self.get_maximum_gold_from(grid, set(), i, j) for i, j in product(range(m), range(n)))