> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/recursion-and-backtracking/10.-path-with-maximum-gold.md).

# 11. Path with Maximum Gold

In a gold mine `grid` of size `m * n`, each cell in this mine has an integer representing the amount of gold in that cell, `0` if it is empty.

Return the maximum amount of gold you can collect under the conditions:

* Every time you are located in a cell you will collect all the gold in that cell.
* From your position you can walk one step to the left, right, up or down.
* You can't visit the same cell more than once.
* Never visit a cell with `0` gold.
* You can start and stop collecting gold from **any** position in the grid that has some gold.

**Example 1:**

```
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.
```

**Example 2:**

```
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
```

## Solution: (Backtracking)

```cpp
class Solution
{
public:
    int dfs(vector<vector<int>> v, int i, int j, int sum)
    {
        int n = v.size();
        int m = v[0].size();
        sum = sum + v[i][j];
        int maxSum = sum;
        v[i][j] = 0;

        vector<int> dir{0, 1, 0, -1, 0};

        for (int k = 0; k < 4; k++)
        {
            int x = i + dir[k];
            int y = j + dir[k + 1];

            if (x >= 0 && x < n && y >= 0 && y < m && v[x][y] != 0)
            {
                 int val = dfs(v, x, y, sum);
                 maxSum = max(maxSum,val);
            }
        }

        return maxSum;
    }
    
    int getMaximumGold(vector<vector<int>> &grid)
    {

        int n = grid.size();
        int m = grid[0].size();
        int maxGold = INT_MIN;
        int sum = 0;
        for (int i = 0; i < n; i++)
        {

            for (int j = 0; j < m; j++)
            {

                if (grid[i][j] != 0)
                {
                    int gold = dfs(grid, i, j, sum);
                    maxGold = max(gold, maxGold);
                }
            }
        }

        return maxGold;
    }
};
```