洪水灌溉算法-岛屿相关问题

岛屿问题的理解

岛屿系列算法问题是经典的面试高频题，虽然基本的问题并不难，但是这类问题有一些有意思的扩展，比如求子岛屿数量，求形状不同的岛屿数量等等。

岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。

那么如何在二维矩阵中使用 DFS 搜索呢？如果你把二维矩阵中的每一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构。

代码模板框架：

// 二叉树遍历框架
void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

// 二维矩阵遍历框架
void dfs(int[][] grid, int i, int j, boolean[][] visited) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (visited[i][j]) {
        // 已遍历过 (i, j)
        return;
    }

    // 进入当前节点 (i, j)
    visited[i][j] = true;

    // 进入相邻节点（四叉树）
    // 上
    dfs(grid, i - 1, j, visited);
    // 下
    dfs(grid, i + 1, j, visited);
    // 左
    dfs(grid, i, j - 1, visited);
    // 右
    dfs(grid, i, j + 1, visited);
}

本文涉及到的参考题目:

1.岛屿的数量 https://leetcode.cn/problems/number-of-islands/description/

2.封闭岛屿的数量 https://leetcode.cn/problems/number-of-closed-islands/description/

3.飞地的数量 https://leetcode.cn/problems/number-of-enclaves/

4.岛屿的最大面积 https://leetcode.cn/problems/max-area-of-island/description/

5.统计子岛屿的数量 https://leetcode.cn/problems/count-sub-islands/description/

6.找到所有的农场组 https://leetcode.cn/problems/find-all-groups-of-farmland/description/

下面以一些题目对岛屿问题的模板进行使用和练习。

---

 一、 岛屿数量

题目描述：

题目分析:

本题中用1代表陆地，用0代表水，要计算的是岛屿数量。连成片的陆地形成岛屿，在FloodFill算法中，避免使用visited数组的做法是每次遍历到图中的陆地，就会用dfs遍历，将该陆地所在的岛屿中的陆地全部覆盖一遍，也就是说，每个岛屿中只有一个陆地用来计数(计岛屿的数量)，其他的陆地都受该陆地的影响而淹没了，有一种牵一发而动全身的感觉hh.具体细节看代码：

代码:

class Solution {
    public void dfs(char[][] grid, int i, int j) {
        int n = grid.length, m = grid[0].length;

        if(i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '0') return ;

        // 将当前岛屿淹没
        grid[i][j] = '0';
        // 四面八方淹没
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i ,j + 1);
    }
    public int numIslands(char[][] grid) {
        int n = grid.length, m = grid[0].length;
        int res = 0; // 存储岛屿的个数

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1') {
                    res++; // 当前遍历到的网格为1 表示他是一个岛屿
                    dfs(grid, i, j); // 洪水灌溉 将当前陆地板块所有的陆地都变成0 防止当前岛屿重复遍历
                }
            }
        return res;

    }
}

---

二、 封闭岛屿的数量

题目分析：

与上一个题不同的是，本题中图元素之外的部分没有被海水包围，而且要求的岛屿数量是封闭岛屿-也就是说上图中的边界四周都不能构成封闭的岛屿，与此同时与这些边界中陆地而相连接的陆地，也不能构成封闭岛屿，所以要求解本题，需要在上一题的基础上，先对边界进行处理淹没(包括淹没边界上本来是陆地的部分和与边界上陆地相连接的内部陆地)，然后剩余的陆地便就是封闭岛屿。

代码：

class Solution {
    public void dfs(int[][] grid, int i, int j) {
        int n = grid.length;
        int m = grid[0].length;

        if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == 1) return ;

        grid[i][j] = 1;
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
    public int closedIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        // 对于靠边的岛屿直接淹没即可 这种靠边的岛屿不可能是封闭岛屿 也不能让他们对里面的陆地造成影响
        for(int i = 0; i < n; i++) {
            dfs(grid, i, 0); // 淹没第一列
            dfs(grid, i, m - 1);// 淹没最后一列
        }

        for(int j = 0; j < m; j++) {
            dfs(grid, 0, j); // 淹没第一行
            dfs(grid, n - 1, j);// 淹没最后一行
        }

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 0) {
                    dfs(grid, i, j);
                    ans++;
                }
            }
        
        return ans;
    }
}

---

三、 飞地的数量

题目分析：

本文与封闭岛屿一题相似，转换一下题目含义即可。覆盖边界情况和边界情况相连接的陆地后 剩余的陆地表示全被0包围 也就是无法离开网格边界的陆地单元。

代码:

class Solution {
    public int numEnclaves(int[][] grid) {
        int n = grid.length, m = grid[0].length;

        int res = 0;

        // 覆盖边界情况和边界情况相连接的陆地后 剩余的陆地表示全被0包围 也就是无法离开网格边界的陆地单元

        for(int j = 0; j < m; j++) {
            dfs(grid, 0, j);
            dfs(grid, n - 1, j);
        }

        for(int i = 0; i < n; i++){
            dfs(grid, i, 0);
            dfs(grid, i, m - 1);
        }

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(grid[i][j] == 1)
                    res++;
        
        return res;
    }

    public void dfs(int[][] grid, int i, int j) {
        int n = grid.length, m = grid[0].length;

        if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == 0) return ;

        grid[i][j] = 0;

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}

---

四、岛屿的最大面积

题目分析:

对于本题，与前面的统计岛屿的数量不同，本题统计的是所有岛屿中的最大陆地的个数，需要单独维护一下每个岛屿中的陆地个数，写法上让dfs返回该岛屿的陆地个数，具体见代码.

代码：

class Solution {
    public int dfs(int[][] grid, int i, int j) {
        int n = grid.length, m = grid[0].length;

        if(i < 0 || j < 0 || i >=  n || j >= m || grid[i][j] == 0) return 0;

        grid[i][j] = 0;
        // 统计当前陆地四个方向中相连接的陆地个数
        int cnt = dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
        // 最后返回的是加上自己这块陆地的个数 也就是岛屿中的总陆地个数
        return cnt + 1;
    }
    public int maxAreaOfIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;

        int res = 0;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 1) {
                    // 求最大值，统计每块岛屿的陆地个数 进行取max
                    res = Math.max(res, dfs(grid, i, j));
                }
            }
        return res;
    }
}

---

五、统计子岛屿

题目分析：

这道题的关键在于，如何快速判断子岛屿？

什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛？

当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。

反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。

那么，我们只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。这道题的思路和计算「封闭岛屿」数量的思路有些类似，只不过后者排除那些靠边的岛屿，前者排除那些不可能是子岛的岛屿。

具体细节见代码：

代码： 

class Solution {
    public void dfs(int[][] grid, int i, int j) {
        int n = grid.length, m = grid[0].length;

        if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == 0) return ;
        
        grid[i][j] = 0;

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int n = grid1.length, m = grid1[0].length;
        //当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
        //反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。
        // 剩余的grid2中的岛屿表示一定是grid1的子岛屿
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                // 表示在grid2中存在grid2是陆地但是grid1是水域
                if(grid1[i][j] == 0 && grid2[i][j] == 1)    
                    dfs(grid2, i, j); // 直接淹没grid2这片岛屿
            }

        int ans = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(grid2[i][j] == 1) {
                    dfs(grid2, i, j);
                    ans++;
                }
            }
        
        return ans;
    }
}

---

六、找到所有的农场组

题目分析:

一开始拿到这个题有点不知道怎么下手，静下心来仔细想想其实也是FloodFill算法的变形题，只不过本题需要返回每个岛屿的左上角和右下角的坐标，如果我们直接按顺序遍历当前图，那么第一个得到的为1的元素的坐标一定是左上角坐标，那么问题就变成了怎么维护每个岛屿右下角元素的坐标。其实也不难，只需要对于当前的岛屿，每次进行淹没操作之前维护一下当前岛屿里右下角的坐标，然后四面八方的淹没，整片岛屿淹没完以后，得到的最大的坐标即需要返回的坐标。值得一提的是我在代码里使用了List<int[]>类型，注意最后还需要转换成二维数组的形式，具体见代码;

代码： 

class Solution {
    int x2, y2 = 0;
    List<int[]> list = new ArrayList<>();
    public void dfs(int[][] land, int i,int j) {
        int n = land.length;
        int m = land[0].length;

        if(i < 0 || j < 0 || i >= n || j >= m || land[i][j] == 0) return ;

        x2 = Math.max(x2, i);
        y2 = Math.max(y2, j);

        land[i][j] = 0;

        dfs(land, i - 1, j);
        dfs(land, i + 1, j);
        dfs(land, i, j - 1);
        dfs(land, i, j + 1);

    }
    public int[][] findFarmland(int[][] land) {
        int n = land.length, m = land[0].length;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++){
                if(land[i][j] == 1) {
                    x2 = i;
                    y2 = j;

                    dfs(land, i, j);

                    list.add(new int[]{i, j, x2, y2});
                }
            }
        
        return list.toArray(new int[list.size()][]);
    }
}