Path with Maximum Gold for coding interview round

New update is available. Click here to update.

Last Updated: 28 Feb, 2021

Path with Maximum Gold

Moderate

Solve now

Problem statement

You’re given a 2 dimensional array 'GRID' of N * M size, representing a Gold mine. Each cell of this grid contains an integer that represents the amount of gold present in that cell.

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.

Solve now

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:

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.
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.
6. Return answer.
Return maxGold