YSMull
<-- home

岛屿上的DFS总结

200.岛屿数量(medium)

题目链接:leetcode 200.岛屿数量

class Solution {

    public void fill(char[][] grid, int i, int j) {
        if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0) return;
        if (grid[i][j] != '1') return;
        grid[i][j] = '2';
        fill(grid, i, j + 1);
        fill(grid, i, j - 1);
        fill(grid, i + 1, j);
        fill(grid, i - 1, j);
    }

    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    res += 1;
                    fill(grid, i, j);
                }
            }
        }
        return res;
    }
}

463.岛屿的周长(easy)

题目链接: leetcode 463.岛屿的周长

思路:某个 grid 为 0 的位置,考察其四周,如果是水或者是边界,则周长加 1

方法一:遍历

class Solution {

    public int isBorderOrWater(int[][] grid, int i, int j) {
        if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0)
            return 1;
        if (grid[i][j] == 0)
            return 1;
        return 0;
    }

    public int islandPerimeter(int[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    res += (
                        isBorderOrWater(grid, i, j + 1) + 
                        isBorderOrWater(grid, i + 1, j) + 
                        isBorderOrWater(grid, i - 1, j) + 
                        isBorderOrWater(grid, i, j - 1)
                    );
                    
                }
            }
        }
        return res;
    }
}

方法二:DFS

class Solution {

    public int dfs(int[][] grid, int i, int j) {
        if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0)
            return 1;
        if (grid[i][j] == 0)
            return 1;
        if (grid[i][j] == 2)
            return 0;
        grid[i][j] = 2;
        return dfs(grid, i, j + 1) +
                dfs(grid, i, j - 1) +
                dfs(grid, i + 1, j) +
                dfs(grid, i - 1, j);
    }

    public int islandPerimeter(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return dfs(grid, i, j);
                }
            }
        }
        return 0;
    }
}

695.岛屿的最大面积(medium)

题目链接: leetcode 695.岛屿的最大面积

class Solution {

    public int dfs(int[][] grid, int i, int j) {
        if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0)
            return 0;
        if (grid[i][j] != 1)
            return 0;
        grid[i][j] = 2;
        return 1 + dfs(grid, i, j + 1) +
                dfs(grid, i, j - 1) +
                dfs(grid, i + 1, j) +
                dfs(grid, i - 1, j);
    }

    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    max = Math.max(max, dfs(grid, i, j));
                }
            }
        }
        return max;
    }
}

827.最大人工岛(hard)

题目链接: leetcode 827.最大人工岛

对于每个为 1 的格子,第一次 dfs,记录其属于哪个岛屿,以及其面积,然后再遍历每个 grid 为 0 的位置,考察此处补 0 之后,形成的新岛屿的面积。
(新面积为1 + 四周不同 index 的岛屿的面积之和)

class Solution {

    public int dfs(int[][] grid, int i, int j, int areaIndex) {
        if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0)
            return 0;
        // 要么是别人的岛屿,要么是自己已访问过
        if (grid[i][j] != 1)
            return 0;
            
        // trick,记录是第几个岛屿
        grid[i][j] = areaIndex + 2;
        return 1 + dfs(grid, i, j + 1, areaIndex) +
                dfs(grid, i, j - 1, areaIndex) +
                dfs(grid, i + 1, j, areaIndex) +
                dfs(grid, i - 1, j, areaIndex);
    }

    public int largestIsland(int[][] grid) {
        int areaIndex = 0;
        int[] areas = new int[grid.length * grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j, areaIndex);
                    areas[areaIndex] = area;
                    areaIndex++;
                }
            }
        }

        int max = areas[0];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> set = new HashSet<>();
                    if (i - 1 >= 0 && i - 1 < grid.length && grid[i-1][j] > 1) set.add(grid[i-1][j]);
                    if (i + 1 >= 0 && i + 1 < grid.length && grid[i+1][j] > 1) set.add(grid[i+1][j]);
                    if (j - 1 >= 0 && j - 1 < grid[0].length && grid[i][j-1] > 1) set.add(grid[i][j-1]);
                    if (j + 1 >= 0 && j + 1 < grid[0].length && grid[i][j+1] > 1) set.add(grid[i][j+1]);
                    int newArea = 1;
                    for (Integer index : set) {
                        newArea += areas[index - 2];
                    }
                    max = Math.max(max, newArea);
                }
            }
        }
        return max;
    }
}

1254.统计封闭岛屿的数目(medium)

题目链接: leetcode 1254.统计封闭岛屿的数目

方法一:灌水法

第一次 dfs,先从边界处所有为 0 的位置,往连通的 0 处灌水,此时剩余的 0 一定都是被 1 包裹的
第二次 dfs,从内部剩余的每个为 0 的位置,通过灌水,统计有多少个不同的连通的 0 区域

class Solution {

    public void fill(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length)
            return;
        if (grid[i][j] == 1)
            return;
        if (grid[i][j] == 0) {
            grid[i][j] = 1;
        }
        fill(grid, i + 1, j);
        fill(grid, i - 1, j);
        fill(grid, i, j + 1);
        fill(grid, i, j - 1);
    }

    public int closedIsland(int[][] grid) {
        int res = 0;

        // 先从四周灌水
        for (int i = 0; i < grid.length; i++) {
            if (grid[i][0] == 0) {
                fill(grid, i, 0);
            }
            if (grid[i][grid[0].length - 1] == 0) {
                fill(grid, i, grid[0].length - 1);
            }
        }

        for (int j = 0; j < grid[0].length; j++) {
            if (grid[0][j] == 0) {
                fill(grid, 0, j);
            }
            if (grid[grid.length - 1][j] == 0) {
                fill(grid, grid.length - 1, j);
            }
        }

        // 再从内部灌水
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    fill(grid, i, j);
                    res += 1;
                }
            }
        }
        return res;
    }
}

方法二:判断是否可逃逸

对于每个 0,都判断其是否可以逃逸到边界,如果不可以,则认为其被 1 包围了

注意,我一开始在 dfs 里把内联了,导致总是 WA

class Solution {

    public boolean escape(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return true;
        if (grid[i][j] == 1) return false;
        // 走过
        if (grid[i][j] == 2) return false;
        grid[i][j] = 2;
        
        // !!注意下面的代码不可以内联,否则会因为逻辑运算符截断少遍历一些位置
        boolean a = escape(grid, i + 1, j);
        boolean b = escape(grid, i - 1, j);
        boolean c = escape(grid, i, j + 1);
        boolean d = escape(grid, i, j - 1);
        return a || b || c || d;
    }

    public int closedIsland(int[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    if (!escape(grid, i, j)) {
                        res += 1;
                    }
                }
            }
        }
        return res;
    }
}

参考资料