为何遍历一次后网格变为零？金矿最大采金量算法疑问

问题背景 #

给定一个m×n的金矿网格，每个单元格包含整数代表黄金储量，0表示空单元格。需返回符合以下条件的最大采金量：

• 每次到达单元格时收集全部黄金
• 可向上下左右四个方向移动一步
• 不可重复访问同一单元格
• 禁止访问黄金储量为0的单元格
• 可从任意有黄金的位置开始或停止采金

用户疑问 #

针对以下Java实现代码，为何执行一次遍历后网格会变为零？

class Solution {
    public int getMaximumGold( int[][] grid) {
         int max=0, min=0;
       for(int i=0; i<grid.length; i++){
           for(int j=0; j<grid[i].length; j++){
           
              min=gold(grid, i, j);
               max=Math.max(max, min);
               
           }
       }
       
       
        return max;
    }
    public int gold(int[][] grid,int row, int col) {
        if(grid[row][col]==0) return 0;
        int max=0, min=0; 
       int [][] newgrid = grid;
        int currgold = newgrid[row][col];
        
        newgrid[row][col]=0;
        //left check
        if(col-1>=0 && newgrid[row][col-1]!=0) {
            int[][] ogrid = newgrid;
            max=gold(ogrid,row,col-1);
        }
        //right check
        if(col+1<newgrid[row].length && newgrid[row][col+1]!=0) {
            int[][] ogrid = newgrid;
            min=gold(ogrid,row,col+1);
        }
        max=Math.max(max,min);
        //up check
        if(row-1>=0 && newgrid[row-1][col]!=0) {
            int[][] ogrid = newgrid;
            min=gold(ogrid,row-1,col);
            }
        max=Math.max(max,min);
        //downcheck
        if(row+1<newgrid.length && newgrid[row+1][col] != 0) {
            int[][] ogrid = newgrid;
            min = gold(ogrid, row+1, col);
        }
        
        return Math.max(max,min)+currgold;
    }
}

原因分析 #

1. 数组引用传递的特性：Java中数组属于引用类型，代码里int[][] newgrid = grid;并没有创建新的数组，只是让newgrid指向了原grid数组的内存地址。后续对newgrid的所有修改，本质上都是直接修改原grid数组的内容。

2. 缺少回溯恢复操作：在gold方法中，进入递归时会执行newgrid[row][col]=0，目的是标记当前单元格已访问，避免重复进入。但问题在于，递归结束后没有把这个单元格的值恢复为原来的currgold。这就导致第一次遍历（包括递归过程）会把所有走过的单元格都设为0，后续的循环遍历或者递归调用看到的都是被修改后的全零网格。

修正思路 #

不需要复制整个数组，只需要在递归前后做回溯处理：

• 递归前记录当前单元格的黄金储量
• 把当前单元格设为0标记已访问
• 递归完成后，将单元格的值恢复为原来的储量

修改后的gold方法示例：

public int gold(int[][] grid,int row, int col) {
    if(row < 0 || row >= grid.length || col <0 || col >= grid[0].length || grid[row][col]==0) 
        return 0;
    
    int currgold = grid[row][col];
    // 标记已访问
    grid[row][col] = 0;
    
    // 递归遍历四个方向
    int left = gold(grid, row, col-1);
    int right = gold(grid, row, col+1);
    int up = gold(grid, row-1, col);
    int down = gold(grid, row+1, col);
    
    // 回溯恢复值
    grid[row][col] = currgold;
    
    // 返回当前黄金加上四个方向的最大值
    return currgold + Math.max(Math.max(left, right), Math.max(up, down));
}

内容的提问来源于stack exchange，提问作者Aniket Ingawale