# 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;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/recursion-and-backtracking/10.-path-with-maximum-gold.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.