1219. Path with Maximum Gold | 1663

 1class Solution:
 2    def getMaximumGold(self, grid: List[List[int]]) -> int:
 3        # intuition:
 4        # bfs from every cell that's not 0
 5        # keep a global max, which is the answer
 6        # keep a visited set() for each bfs
 7
 8        # BFS does not work easily.
 9        # example:
10        # [1,2,3],
11        # [2,0,4],
12        # [7,6,5],
13        # [8,0,6],
14        # [9,8,7]
15        # one possible solution: 2-1-2-3-4-5-6-7-8-9-8-7-6
16        # why BFS fails:
17        # 2-7-6-5
18        # 2-1-2-3-4-dead
19
20        # NOTE: BFS with a single `visited` set per start is incorrect here.
21        # "Visited" is per *path*, not per *cell*:
22        # two different paths can end at the same cell but have visited
23        # different other cells before it. A BFS that only stores (r, c)
24        # and a global `visited` set will merge those states and prune
25        # valid paths. DFS + backtracking is a natural fit because each
26        # recursive call has its own visited history (via mark/unmark).
27
28        result = 0
29        m, n = len(grid), len(grid[0])
30
31        def dfs(loc, gold, visited):
32            x, y = loc
33
34            if (
35                loc in visited
36                or x < 0
37                or x > m - 1
38                or y < 0
39                or y > n - 1
40                or grid[x][y] == 0
41            ):
42                return gold
43
44            gold += grid[x][y]
45
46            visited.add(loc)
47            best = max(
48                dfs((x, y + 1), gold, visited),
49                dfs((x + 1, y), gold, visited),
50                dfs((x, y - 1), gold, visited),
51                dfs((x - 1, y), gold, visited),
52            )
53            visited.remove(loc)
54
55            return best
56
57        for x in range(m):
58            for y in range(n):
59                possibility = dfs((x, y), 0, set())
60                if possibility > result:
61                    result = possibility
62
63        return result