1
# Runtime: 1480 ms (Top 97.21%) | Memory: 14.1 MB (Top 13.08%)
2
class Solution:
3
    def getMaximumGold(self, grid):
4
        answer = [0]
5

6
        def visit(visited, i, j, gold_sum):
7
            val = grid[i][j]
8
            if val == 0 or (i, j) in visited:
9
                answer[0] = max(answer[0], gold_sum)
10
                return
11

12
            gold_sum_new = gold_sum + val
13
            visited_new = visited.union({(i, j)})
14

15
            if i > 0:
16
                visit(visited_new, i - 1, j, gold_sum_new)
17

18
            if j < len(grid[i]) - 1:
19
                visit(visited_new, i, j + 1, gold_sum_new)
20

21
            if i < len(grid) - 1:
22
                visit(visited_new, i + 1, j, gold_sum_new)
23
            if j > 0:
24
                visit(visited_new, i, j - 1, gold_sum_new)
25

26
        # choosing the starting points
27
        for i in range(len(grid)):
28
            for j in range(len(grid[i])):
29
                if grid[i][j] != 0:
30
                    count = 0
31

32
                    try:
33
                        if grid[i - 1][j] != 0:
34
                            count += 1
35
                    except:
36
                        pass
37
                    try:
38
                        if grid[i][j + 1] != 0:
39
                            count += 1
40
                    except:
41
                        pass
42
                    try:
43
                        if grid[i + 1][j] != 0:
44
                            count += 1
45
                    except:
46
                        pass
47
                    try:
48
                        if grid[i][j - 1] != 0:
49
                            count += 1
50
                    except:
51
                        pass
52

53
                    if count < 3:
54
                        visit(set(), i, j, 0)
55

56
        return answer[0]