LeetCode 695 岛屿最大面积JS递归实现异常及shadowGrid问题求助

问题根源 #

1. shadowGrid 初始化引用错误 #

你创建shadowGrid时用的写法存在引用共享问题：

var shadowGrid = Array(grid.length).fill(Array(grid[0].length).fill(0))

JS中Array.fill()如果填充的是引用类型（比如数组），会把同一个引用的实例复制给所有元素。也就是说你这个shadowGrid里的8行，本质上是指向同一个数组的指针，你修改任意一行的shadowGrid[i][j]，所有行的第j位都会同步修改，这就是你最后看到所有行完全一致的核心原因。
正确的初始化方式是给每一行单独创建新数组：

var shadowGrid = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(0))

2. 重复调用countLand导致计算错误 #

你在双重for循环里连续调用了两次countLand(idR, idC)：

console.log(`countLand: ${countLand(idR, idC)},  grid[idR][idC] = ${grid[idR][idC]},  islandSize : ${islandSize}`);
islandSize = Math.max(countLand(idR, idC), islandSize);

第一次调用countLand的时候，已经把当前岛屿所有关联的格子都在shadowGrid里标记为已访问，第二次调用的时候直接命中判断条件返回0，等于你完全没有拿到第一次计算出来的正确面积值，最终islandSize的计算完全错误。
修正方式是把countLand的结果存到临时变量里，只调用一次：

const currentSize = countLand(idR, idC);
console.log(`countLand: ${currentSize},  grid[idR][idC] = ${grid[idR][idC]},  islandSize : ${islandSize}`);
islandSize = Math.max(currentSize, islandSize);

修正后完整代码 #

function maxAreaOfIsland(grid){
    // 修正初始化方式，每行单独创建新数组
    var shadowGrid = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(0)),
        islandSize = 0;
    function countLand(idR, idC){
        if(idR < 0 || idR >= grid.length || idC < 0 || idC >= grid[0].length || shadowGrid[idR][idC] == 1 || grid[idR][idC] == 0 ){
            return 0;
        }
        shadowGrid[idR][idC] = 1;
        return 1 +  countLand(idR-1, idC) + countLand(idR+1, idC) + countLand(idR, idC-1) + countLand(idR, idC+1);
    }
    for(let idR = 0; idR < grid.length; idR++){
        for(let idC = 0; idC < grid[0].length; idC++){
            // 只调用一次countLand，存到临时变量
            const currentSize = countLand(idR, idC);
            islandSize = Math.max(currentSize, islandSize);
        }
    }
    return islandSize;
}
var grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
            [0,0,0,0,0,0,0,1,1,1,0,0,0],
            [0,1,1,0,1,0,0,0,0,0,0,0,0],
            [0,1,0,0,1,1,0,0,1,0,1,0,0],
            [0,1,0,0,1,1,0,0,1,1,1,0,0],
            [0,0,0,0,0,0,0,0,0,0,1,0,0],
            [0,0,0,0,0,0,0,1,1,1,0,0,0],
            [0,0,0,0,0,0,0,1,1,0,0,0,0]];
console.log(maxAreaOfIsland(grid)); // 输出正确结果6

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