Path with Maximum Gold

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.

The optimal way to collect maximum gold is 9->3->1->2->3->2->3, or we start from the 2nd element of the first column, i.e. ‘3’ and follow the path 3->2->3->2->1->3->9, either way, we’ll get the same amount of gold.

Backtracking

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

Time Complexity

O(K * (3 ^ K)), where K is the number of cells that have gold.

For each cell with non-zero gold, there are a maximum number of three possible neighbors that we can visit, and since there are K such cells, our final time complexity will be O(K * (3 ^ K)).

Space Complexity

O(K), where K is the number of cells that have gold.

In the worst case, there will be a maximum K states in the recursion stack space. Hence the final space complexity will be O(K).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation of Sample Input 2: