[数据结构与算法]DFS - leetcode-岛屿问题（合集）

在 leetcode 上写 DFS 时，看到了 nettee 老哥的-DFS 框架，于是写了几道 岛屿问题 练练手

岛屿问题：

• 200. 岛屿数量
  • 三种解法：DFS、BFS、并查集（这里主要记录 DFS）
• 463. 岛屿的周长
• 695. 岛屿的最大面积
• 827. 最大人工岛

200. 岛屿数量

本质上就是 求图中 连通分量的个数

求图中 连通分量个数的方法（3 种）：

• DFS
• BFS
• 并查集

详细题解，见 DFS & BFS & 并查集 -leetcode-200. 岛屿数量

463. 岛屿的周长

本题 求的是 连通分量的最外侧周长

思路：

• 数据较小， [1, 100]，直接 dfs 爆搜，即可
• 由图可知，如果当前是陆地，并且从当前位置 扩展的“新位置”是“水坑”或“新位置“越界，则会为周长贡献一条边；否则（即，新位置已经被遍历过了），不会为 周长贡献 边

这里使用的是 zju_ds dfs 魔板，当然本题也可以采用 nettee 老哥的-DFS 框架 + 带有返回值 inrt 的 DFS （见 827. 最大人工岛 代码）

class Solution {
    // 上下左右 4 个方向
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};
    // 全局变量
    int[][] grid;
    boolean[][] visited;
    int m; // 行
    int n; // 列
    int res = 0; // 岛屿周长

    public int islandPerimeter(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    dfs(i, j);
                }
            }
        }
        return res;
    }

    public void dfs(int x, int y) {
        visited[x][y] = true; // 标记
        for (int i = 0; i < 4; i++) {
            int xx = x + dirx[i];
            int yy = y + diry[i];
            // 当前是陆地，并且从当前位置 扩展的“新位置”是“水坑”或“新位置“越界，则会为周长贡献一条边
            // System.out.println("xx = " + xx);
            // System.out.println("yy = " + yy);
            if (xx < 0 || xx >= m || yy < 0 || yy >= n || grid[xx][yy] == 0) {
                res++;
                continue;
            }
            if (visited[xx][yy]) { // 此时不会为周长“贡献“一条边
                continue;
            }
            dfs(xx, yy);
        }
    }
}

695. 岛屿的最大面积

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

本题其实就是求 “最大”（顶点数最多）的连通分量

思路：

• 数据较小， [1, 50]，直接经典 dfs 爆搜，即可
• 经典 DFS 求每个连通分量的个数，然后取最大值

这里使用的是 zju_ds dfs 魔板，当然本题也可以采用 nettee 老哥的-DFS 框架 + 带有返回值 inrt 的 DFS （见 827. 最大人工岛 代码）

class Solution {
    // 上下左右 4 个方向
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};
    // 全局变量
    int[][] grid;
    boolean[][] visited;
    int m; // 行
    int n; // 列
    int area; // 当前所在岛屿的面积
    int maxArea = 0; // 岛屿最大面积

    public int maxAreaOfIsland(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    area = 1;
                    dfs(i, j);
                    maxArea = Math.max(area, maxArea);
                }
            }
        }
        return maxArea;
    }

    public void dfs(int x, int y) {
        visited[x][y] = true; // 标记
        for (int i = 0; i < 4; i++) {
            int xx = x + dirx[i];
            int yy = y + diry[i];
            // System.out.println("xx = " + xx);
            // System.out.println("yy = " + yy);
            if ((xx < 0 || xx >= m || yy < 0 || yy >= n) || visited[xx][yy] || grid[xx][yy] == 0) {
                continue;
            }
            // “有效的“ dfs 次数，即为当前所在岛屿的 面积
            area++;
            dfs(xx, yy);
        }
    }
}

827. 最大人工岛

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] 为 0 或 1

思路：

• DFS 尝试填充每一个 “水坑”，然后取最大值。 TLE
• 两次 DFS + 哈希表 + 染色 AC

DFS 尝试填充每一个 “水坑” TLE

错误做法 1：求 top2 的连通分量 WA

• 最开始想的是，类似 695. 岛屿的最大面积 求 top2 的连通分量，然后加一。后来一想，觉得不可，因为 为这两个 top2 的岛屿 添加一个“陆地”后 不一定 连通

错误做法 2：DFS 尝试填充每一个 “水坑” TLE

• 将当前海洋格子 “填海造陆” gird[i][j] = 1 (即，一次填海造陆） ；
• 然后从当前 “海洋格子” 出发 DFS 求连通分量的顶点数；
• 本次 DFS 完事后，需要进行回溯（即，gird[i][j] = 0，将 填的海洋 还原回去，以待后面其他位置 “填海造陆” ）

注意：这里不同于 “岛屿数量” & “岛屿最大面积”（只用 visited 全局初始化一次），这里每次以 (i, j) 水坑开始 dfs 之前，都要初始化 visited

但是，这样写超时了

class Solution {
    // 上下左右 4 个方向
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};
    // 全局变量
    int[][] grid;
    boolean[][] visited;
    int m; // 行
    int n; // 列
    int area; // 当前所在岛屿的面积
    int maxArea = 0; // 岛屿最大面积

    public int largestIsland(int[][] grid) {
        for (int[] line : grid) {
            System.out.println(Arrays.toString(line));
        }
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) { // 尝试填充每个 水坑
                    // 这里不同于 “岛屿数量” & “岛屿最大面积”（只用 visited 全局初始化一次）
                    // 这里每次以 (i, j) 水坑开始 dfs 之前，都要初始化 visited
                    for (boolean[] line : visited) {
                        Arrays.fill(line, false);
                    }

                    System.out.println("----------------");
                    System.out.println("i = " + i);
                    System.out.println("j = " + j);
                    grid[i][j] = 1; // 将当前 “水坑” 填成“陆地”
                    area = 1;
                    dfs(i, j);
                    grid[i][j] = 0; // 回溯
                    System.out.println("area = " + area);
                    maxArea = Math.max(area, maxArea);
                }
            }
        }
        return maxArea == 0 ? m * n : maxArea;
    }

    public void dfs(int x, int y) {
        visited[x][y] = true; // 标记
        for (int i = 0; i < 4; i++) {
            int xx = x + dirx[i];
            int yy = y + diry[i];
            // System.out.println("xx = " + xx);
            // System.out.println("yy = " + yy);
            if ((xx < 0 || xx >= m || yy < 0 || yy >= n) || visited[xx][yy] || grid[xx][yy] == 0) {
                continue;
            }
            // “有效的“ dfs 次数，即为当前所在岛屿的 面积
            // System.out.println("xx = " + xx);
            // System.out.println("yy = " + yy);
            area++;
            dfs(xx, yy);
        }
    }
}

两次 DFS + 哈希表 + 染色 AC

参考 nettee 老哥的-DFS 框架

采用两次遍历

1. 第一次 DFS 遍历 “陆地”，记录每个岛屿的面积

   • 这里将 已经访问过的 岛屿 标记为 “岛屿索引号” index（grid 中已经有 0、1 了，为了区分 所以从 2 开始），而不是面积
   • 采用 map 记录每个岛屿序号为 index 的“面积”

2. 第二次 dfs：遍历海洋格子，尝试将 “海洋格子” 和 周围的 “岛屿” 合并，取 max

   • 找当前海洋格子的邻居节点，如果是两个岛屿 则合并之

采用 nettee 老哥的-DFS 框架，类似二叉树 dfs 魔板 + 哈希表 + 两次遍历 + 染色

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

class Solution {
    // 上下左右 4 个方向
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};
    // 全局变量
    int[][] grid;
    // boolean[][] visited; // 直接利用 grid 标记
    /**
     * 不用 visited 标记，改用 grid 标记访问状态
     * grid[i][j] == 0 ：水坑
     * grid[i][j] == 1 ：陆地
     * grid[i][j] == idnex ：已经访问过的 岛屿，并被标记为 已经访问过
     */
    int m; // 行
    int n; // 列

    public int largestIsland(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        int res = 0;
        int index = 2; // 给岛屿 记录“索引号”（grid 中已经有 0、1 了，为了区分 所以从 2 开始）
        Map<Integer, Integer> map = new HashMap<>(); // 记录每个岛屿的“面积”。key：index；value：岛屿面积
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // 记录每个岛屿的面积
                    int area = dfs(i, j, index); // 局部变量（改用 类似二叉树魔板 + 待返回值的 dfs时，不能将 area 设为全局变量）
                    res = Math.max(res, area);
                    map.put(index++, area); // 记录每个岛屿序号为 index 的“面积”
                }
            }
        }
        System.out.println(map);
        for (int[] g : grid) {
            System.out.println(Arrays.toString(g));
        }
        // 第二次 dfs：遍历海洋格子
        if (res == 0) { // 全是海洋格子
            return 1;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    HashSet<Integer> set = findNeighbors(i, j); // 找当前海洋格子的邻居节点，如果是两个岛屿 则合并之
                    System.out.println("set = " + set);
                    if (set.size() < 1) {
                        continue;
                    }
                    int cnt = 1;
                    for (Integer islandIndex : set) {
                        cnt += map.get(islandIndex);
                    }
                    res = Math.max(cnt, res);
                }
            }
        }
        return res;
    }

    /**
     * 找 (x, y) 所在 “水坑” 上下左右 4 个方向的 岛屿索引号
     * @param x
     * @param y
     * @return
     */
    public HashSet<Integer> findNeighbors(int x, int y) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < 4; i++) {
            int xx = x + dirx[i];
            int yy = y + diry[i];
            if (xx < 0 || xx >= m || yy < 0 || yy >= n || grid[xx][yy] == 0) { // 越界，或者新位置 是“水坑”，则不必看
                continue;
            }
            set.add(grid[xx][yy]); // 收集 (x, y) 邻居 (xx, yy) 所在岛屿的 索引号
        }
        return set;
    }

    public int dfs(int x, int y, int index) {
        // 终止条件（网格出界，类似二叉树走到叶子节点）
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return 0;
        }
        // 避免重复访问
        if (grid[x][y] != 1) { // 此时，从上面的终止条件 下来了，所以 (x, y) 一定不会越界
            return 0;
        }

        grid[x][y] = index; // 标记
        int area = 0;
        for (int i = 0; i < 4; i++) {
            int xx = x + dirx[i];
            int yy = y + diry[i];
            // “有效的“ dfs 次数，即为当前所在岛屿的 面积
            area += dfs(xx, yy, index); // 类似于二叉树，求左右孩子个数之和
        }
        return area + 1; // 类似于二叉树，左右孩子 + 本身，就是以当前节点为 root 的子树节点个数
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 1}, {1, 1}};
        System.out.println(new Solution().largestIsland(grid));
    }
}

这题写的真费劲，太菜了