Why does only backtracking work in this scenario?

Question

I am solving this question on LeetCode.com:

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:-
(a) Every time you are located in a cell you will collect all the gold in that cell;
(b) From your position you can walk one step to the left, right, up or down.
(c) You can't visit the same cell more than once;
(d) Never visit a cell with 0 gold.
(e) You can start and stop collecting gold from any position in the grid that has some gold.
For the grid: [[0,6,0],[5,8,7],[0,9,0]] the output is: 24.

I wrote the code below:

class Solution {
public:
    int dig(vector<vector<int>>& grid, int i, int j) {
        if(i>=grid.size() || i<0 || j>=grid[0].size() || j<0 || grid[i][j]==0) return 0;
        
        //change begins...
        int gold=0;
        gold+=grid[i][j];
        grid[i][j]=0;
        gold+=max(dig(grid, i+1, j), max(dig(grid, i, j+1), max(dig(grid, i-1, j), dig(grid, i, j-1))));
        return gold;
        //change ends...
    }
    
    int getMaximumGold(vector<vector<int>>& grid) {
        vector<vector<int>> gridCopy=grid;
        
        int maxGold=0;
        for(int i=0; i<grid.size(); i++) {
            for(int j=0; j<grid[0].size(); j++) {
                if(grid[i][j]!=0) {
                    maxGold=max(maxGold, dig(gridCopy, i, j));
                    gridCopy=grid;
                }
            }
        }
        
        return maxGold;
    }
};

However, it breaks on the input [[1,0,7,0,0,0],[2,0,6,0,1,0],[3,5,6,7,4,2],[4,3,1,0,2,0],[3,0,5,0,20,0]]; yielding 58 instead of 60.

There's another code that I found here, which is identical, except in the commented part above, wherein they have the below lines instead:

  g[i][j] = -g[i][j];
  auto res = max({ dfs(g, i + 1, j), dfs(g, i, j + 1), dfs(g, i - 1, j), dfs(g, i, j - 1) });
  g[i][j] = -g[i][j];
  return g[i][j] + res;

(And of course, they don't assign grid to gridCopy in the nested for loop, since they revert the modified grid back to its original form).

I understand they are backtracking, while I am not. But I am unable to understand what I am doing incorrect, since logically, I am doing the exact same thing. I used debug statements to trace the issue, but it is becoming difficult to follow along since there are many recursive calls.

Could someone please point out what is the logical fallacy in my code above?

Thanks!

Answer 1

All your recursive calls might modify the grid, and don't restore it.
That means that the first visit to a cell will block it for all other subsequent attempts.

For instance, if dig(grid, i+1, j) is evaluated first, none of the cells that were visited during that computation are available when you do the other three directions.

If your code happens to start in the top left corner and go downwards first in your example, you will visit 1-2-3-4-3 and get stuck.
After that walk, there is no path from the top left corner any more, even though there were plenty of them from the beginning, and some of them pay a lot more than 13.
(You might think that you're going to find a path from either direction, but it depends on the evaluation order.)

Shared mutable state and recursion is a very tricky combination.