1
class Solution {
2
  int r = 0;
3
  int c = 0;
4
  int max = 0;
5

6
  public int getMaximumGold(int[][] grid) {
7
    r = grid.length;
8
    c = grid[0].length;
9
    for (int i = 0; i < r; i++) {
10
      for (int j = 0; j < c; j++) {
11
        if (grid[i][j] != 0) {
12
          dfs(grid, i, j, 0);
13
        }
14
      }
15
    }
16
    return max;
17
  }
18

19
  private void dfs(int[][] grid, int i, int j, int cur) {
20
    if (i < 0 || i >= r || j < 0 || j >= c || grid[i][j] == 0) {
21
      max = Math.max(max, cur);
22
      return;
23
    }
24
    int val = grid[i][j];
25
    grid[i][j] = 0;
26
    dfs(grid, i + 1, j, cur + val);
27
    dfs(grid, i - 1, j, cur + val);
28
    dfs(grid, i, j + 1, cur + val);
29
    dfs(grid, i, j - 1, cur + val);
30
    grid[i][j] = val;
31
  }
32
}