1class Solution {
2    private int dfs(int[][] grid, int x, int y) {
3        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return 0;
4
5        int originalGold = grid[x][y];
6        grid[x][y] = 0; // Mark as visited
7        int maxGold = 0;
8        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
9        for (int[] dir : dirs) {
10            maxGold = Math.max(maxGold, dfs(grid, x + dir[0], y + dir[1]));
11        }
12        grid[x][y] = originalGold; // Backtrack
13        return originalGold + maxGold;
14    }
15
16    public int getMaximumGold(int[][] grid) {
17        int maxGold = 0;
18        for (int i = 0; i < grid.length; i++) {
19            for (int j = 0; j < grid[0].length; j++) {
20                if (grid[i][j] > 0) {
21                    maxGold = Math.max(maxGold, dfs(grid, i, j));
22                }
23            }
24        }
25        return maxGold;
26    }
27}

1