Leetcode封闭岛屿数量问题：递归返回xx/yy结果不同原因咨询

我在解决LeetCode的「封闭岛屿数量」问题时，发现递归代码中返回xx和返回yy会得到不同结果，具体情况如下：

测试用例 #

grid = [[0,0,1,1,0,1,0,0,1,0],[1,1,0,1,1,0,1,1,1,0],[1,0,1,1,1,0,0,1,1,0],[0,1,1,0,0,0,0,1,0,1],[0,0,0,0,0,0,1,1,1,0],[0,1,0,1,0,1,0,1,1,1],[1,0,1,0,1,1,0,0,0,1],[1,1,1,1,1,1,0,0,0,0],[1,1,1,0,0,1,0,1,0,1],[1,1,1,0,1,1,0,1,1,0]]

我的代码 #

class Solution {
    int R;
    int C;
    public int closedIsland(int[][] grid) {
        R = grid.length;
        C = grid[0].length;

        boolean[][] visited = new boolean[R][C];
        int numIslands = 0;
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 1 || visited[r][c]) {
                    continue;
                }
                if (dfs(r, c, grid, visited)) {
                    numIslands++;
                }
                // numIslands += dfs(r, c, grid, visited);
            }
        }

        return numIslands;
    }

    public boolean dfs(int r, int c, int[][] grid, boolean[][] visited) {
        if (r < 0 || r == R || c < 0 || c == C) {
            return false;
        }

        if (grid[r][c] == 1  || visited[r][c]) {
            return true;
        }

        visited[r][c] = true;
    
        boolean left = dfs(r - 1, c, grid, visited);
        boolean right = dfs(r + 1, c, grid, visited);
        boolean up = dfs(r, c - 1, grid, visited);
        boolean bottom = dfs(r, c + 1, grid, visited);
        
        System.out.println(r + "_" + c);
        boolean yy = left && right && up && bottom;
        boolean xx = dfs(r - 1, c, grid, visited) 
                    && dfs(r + 1, c, grid, visited) 
                    && dfs(r, c - 1, grid, visited) && dfs(r, c + 1, grid, visited);
        // System.out.println("yy : " + yy);
        // System.out.println("xx : " + xx);
        // return left && right && up && bottom;
        return xx;
    }
}

差异原因分析 #

核心差异在于是否重复调用DFS：

• yy直接使用第一次调用四个方向DFS得到的结果（left、right、up、bottom）进行逻辑与运算，这四个结果真实反映了每个方向是否触碰到边界或非陆地。
• xx是重新调用四个方向的DFS，此时这些方向的位置已经被标记为visited，返回结果和第一次调用完全不同。

具体细节：

1. 第一次调用四个方向的DFS时，会递归遍历所有相连的0区域，同时将访问过的位置标记为visited=true。如果某个方向触碰到网格边界，该DFS会返回false。
2. 当xx重新调用这些方向的DFS时，目标位置已经处于visited状态，代码会直接返回true（对应if (grid[r][c] == 1 || visited[r][c]) return true;逻辑）。
3. 假设当前岛屿是和边界相连的非封闭岛屿，第一次调用某个方向的DFS会返回false，yy会保留这个false并最终返回false（不会被统计为封闭岛屿）；但xx重新调用时该方向返回true，四个方向都返回true，导致xx错误地返回true，把非封闭岛屿计入统计。

这种重复调用不仅会导致结果错误，还会带来不必要的性能损耗。

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