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)

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