Leetcode 1254 dfs求封闭岛

Question

老师，这道题求解封闭岛数量，深度遍历其中0单元格的情况下，通过逻辑与&&来判断本轮flood的返回结果，如果有一方是越界了，到grid外界了，说明就是isClosed=false,反之for i in dirs都结束后，isClosed还能为true, 说明就是封闭岛，但倒在了25号用例上，我自己认为逻辑是正确的，因为用例数组大，所以想请老师看看哈：）

/**
 * @param {number[][]} grid
 * @return {number}
 */
 const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
var closedIsland = function(grid) {
    //初始化visited访问数组
    let visited = []
    for(let r = 0; r < grid.length; r ++){
        visited[r] = []
        for(let c = 0; c < grid[r].length; c ++){
            visited[r][c] = false;
        }
    }
    const R = grid.length, C = grid[0].length
    let res = 0; // 
    for( let r = 0; r < R; r ++ ){
        for(let c = 0; c < C; c ++){
            if( grid[r][c] == 1 || visited[r][c] ){
                continue;
            }
            //如果dfs返回真，说明岛周围都是1
            if( dfs(grid, r, c, visited) ){
                res ++;
            }
        }
    }
    return res;
};

function dfs( grid, r, c, visited ){

    let isClosed = true; // 初始假定是封闭的
    visited[r][c] = true;

    for( let i = 0; i < dirs.length; i ++ ){
        let nextR = r + dirs[i][0], nextC = c + dirs[i][1];
        if( inArea(grid, nextR, nextC) && !visited[nextR][nextC] && grid[nextR][nextC] == 0 ){
            isClosed = isClosed && dfs(grid, nextR, nextC, visited) // && 有一边是外界就是 isClosed = false
        }else if( !inArea(grid, nextR, nextC) ){
            isClosed = false; // 说明岛有一边是外界
        }
    } // for i

    return isClosed;
}

// r行c列是否在grid范围内
function inArea(grid, r, c){
    if( r >= 0 && r < grid.length && c >= 0 && c < grid[0].length ){
        return true;
    }
    return false;
}

Answer 1

liuyubobobo 2023-06-19 07:36:29

isClosed = isClosed && dfs(grid, nextR, nextC, visited)

在 isClosed == false 的时候，因为逻辑短路，后面的 dfs 不会执行。

修改成：isClosed = dfs(grid, nextR, nextC, visited) && isClosed 即可。

继续加油！：）

• 提问者 甲骨文_0001 #1

  明白了，由于之前的写法，导致同一片联通区域中一部分visited=true，一部分visited=false,从而导致逻辑错误了。谢谢老师开导🙏