New update is available. Click here to update.

Last Updated: 28 Feb, 2021

Moderate

```
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.
```

```
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.
```

```
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.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N, M <= 10
0 <= GRID[i][j] <= 10 ^ 5
Time limit: 1 sec.
```

Approaches

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:**

- Make a function
**maxGold()**, initialise an integer variable**maxGold = 0**to store the maximum amount of gold that we can collect.- Run a loop(loop variable βiβ) from 0 till N.
- Run another loop(loop variable βjβ) inside the above loop from 0 till M.
- 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.

- If grid[i][j] > 0, i.e. this cell contains non zero amount of gold, then update

- 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.- 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.
- 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]. - Update grid[x][y] = 0 so that we donβt visit this cell again.
- 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.** - Update grid[x][y] = count, i.e backtrack.
- Return
**answer.**

- Return
**maxGold**