1
class Solution {
2
 public:
3
  int maxgold = 0;
4
  int m, n;
5
  void gold(int i, int j, vector<vector<int>> &grid, vector<vector<int>> &vis, int count) {
6
    // Down
7
    if (i + 1 < m && !vis[i + 1][j] && grid[i + 1][j]) {
8
      vis[i][j] = 1;
9
      gold(i + 1, j, grid, vis, count + grid[i + 1][j]);
10
      vis[i][j] = 0;
11
    }
12
    // Left
13
    if (j - 1 >= 0 && !vis[i][j - 1] && grid[i][j - 1]) {
14
      vis[i][j] = 1;
15
      gold(i, j - 1, grid, vis, count + grid[i][j - 1]);
16
      vis[i][j] = 0;
17
    }
18
    // Right
19
    if (j + 1 < n && !vis[i][j + 1] && grid[i][j + 1]) {
20
      vis[i][j] = 1;
21
      gold(i, j + 1, grid, vis, count + grid[i][j + 1]);
22
      vis[i][j] = 0;
23
    }
24
    // Up
25
    if (i - 1 >= 0 && !vis[i - 1][j] && grid[i - 1][j]) {
26
      vis[i][j] = 1;
27
      gold(i - 1, j, grid, vis, count + grid[i - 1][j]);
28
      vis[i][j] = 0;
29
    }
30
    maxgold = max(maxgold, count);
31
  }
32

33
  int getMaximumGold(vector<vector<int>> &grid) {
34
    m = grid.size();
35
    n = grid[0].size();
36
    for (int i = 0; i < m; i++) {
37
      for (int j = 0; j < n; j++) {
38
        if (grid[i][j]) {
39
          vector<vector<int>> vis(m, vector<int>(n, 0));
40
          gold(i, j, grid, vis, grid[i][j]);
41
        }
42
      }
43
    }
44
    return maxgold;
45
  }
46
};