New update is available. Click here to update.
Last Updated: 28 Feb, 2021
##### Path with Maximum Gold
Moderate
Problem statement

#### Your task is to return the maximum amount of gold you can collect using the following conditions:

``````1. Every time you reach a cell, you collect all the gold present in that cell.

2. You can go one step left, right, up, or down from your current cellβs position.

3. You canβt visit the cell which you have already visited.

4. You canβt visit a cell with 0 gold.

5. You can choose any cell to start and stop collecting gold.
``````
##### Input Format:
``````The first line of the input contains an integer T denoting the number of test cases.

Each test caseβs first line contains two space-separated integers N and M, denoting the rows and columns in the grid respectively.

The next N lines of each test case contain M space-separated integers denoting the amount of gold present in a cell.
``````
##### Output Format:
``````For every test case, print a single line containing a single integer denoting the maximum amount of gold you can collect.

The output of each test case will be printed in a separate line.
``````
##### Note :
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 5
1 <= N, M <= 10
0 <= GRID[i][j] <=  10 ^ 5

Time limit: 1 sec.
``````
Approaches

## 01Approach

We will perform dfs from each non-zero cell. For each cell with non-zero gold that we visit, weβll visit itβs four possible neighbours and choose the maximum out of these four to get the maximum amount of gold that we collect using backtracking. Since we canβt revisit any cell, weβll mark that as visited and wonβt revisit it.

Algorithm:

1. Make a function maxGold(), initialise an integer variable maxGold = 0 to store the maximum amount of gold that we can collect.
1. Run a loop(loop variable βiβ) from 0 till N.
2. Run another loop(loop variable βjβ) inside the above loop from 0 till M.
1. If grid[i][j] > 0, i.e. this cell contains non zero amount of gold, then update maxGold = max(maxGold, maxGoldHelper(grid, i, j)), to get the maximum gold that we can collect.
2. Now, make a function maxGoldHelper() to perform a depth-first search in the given grid, which will have the given 2d array βgridβ, int βxβ, int βyβ, int βNβ, and int βMβ  as its arguments.
1. Check if the current cell lies within the grid if it doesnβt return 0. If grid[x][y] = 0, weβll also return 0, which indicates that we have already visited this cell.
2. Initialise two integer variables, βanswerβ = 0 and βcountβ = grid[x][y], where βanswerβ will store the maximum amount of gold we can get after going to any of the possible four neighbours from the current position and βcountβ store the amount of gold present in the current cell, i.e. grid[x][y].
3. Update grid[x][y] = 0 so that we donβt visit this cell again.
4. From here, recursively call maxGoldHelper() to all possible unvisited neighbours and store the maximum out of these in βanswerβ and then finally update answer =  answer + count.
5. Update grid[x][y] = count, i.e backtrack.