DFS解决所有岛屿问题

发表于 分类于 ， 阅读次数： Waline： 本文字数： 6.8k 阅读时长 ≈ 6 分钟

岛屿系列题⽬的核⼼考点就是⽤ DFS/BFS 算法遍历⼆维数组。

我们可以根据二叉树遍历框架写出DFS框架。

DFS代码框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(vector<vector<int> >& grid, int i, int j, vector<bool>& visited){
  int m = grid.size(), n = grid[0].size();
  //base case
  if(i < 0 || j < 0 || i >= m || j >= n) return;
  //已经访问过
  if(visited[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);
}

因为⼆维矩阵本质上是⼀幅「图」，所以遍历的过程中需要⼀个 visited 布尔数组防⽌⾛回头路，如果你理解了之后，那么所有的岛屿问题就迎刃而解了。

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例：

输入：grid = []

输出：1

思路：

我们遇到“1”就开始dfs，遍历它的四边，直到没有，我们结果加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    void dfs(vector<vector<char> >& grid, int x, int y){
        //base case
        int m = grid.size(), n = grid[0].size();
        if(x < 0 || y < 0 || x >= m || y < 0 || y >= n) return;
        //已经是水了
        if(grid[x][y] == '0') return;
        //淹没
        grid[x][y] = '0';
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            dfs(grid, nx, ny);
        }
    }
};

为什么每次遇到岛屿，都要⽤ DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。

因为 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不⾛回头路的作用。

1254. 统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

示例：

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]

输出：2

解释：

灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

思路：

注意这道题与上一道题有两个不同的地方

  • 用0代表土地，1代表水
  • 计算的是「封闭岛屿」，上下左右都被1包围的0，也就是说靠边的陆地不算做「封闭岛屿」

那我们先单独处理四边界，把它淹没成水。那么剩下的岛屿就是「封闭岛屿」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int m, n;
    int closedIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        for(int i = 0; i < n; i++){
            //处理上边界
            dfs(grid, 0, i);
            //处理下边界
            dfs(grid, m - 1, i);
        }
        for(int i = 0; i < m; i++){
            //处理左边界
            dfs(grid, i, 0);
            //处理右边界
            dfs(grid, i, n - 1);
        }
        //遍历grid，剩下的岛屿就是封闭岛屿
        int res = 0;
        for(int i = 1; i < m - 1; i++){
            for(int j = 1; j < n - 1; j++){
                if(grid[i][j] == 0){
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    void dfs(vector<vector<int> >& grid, int x, int y){
        //base case
        if(x < 0 || y < 0 || x >= m || y >= n) return;
        if(grid[x][y] == 1) return;
        //淹没
        grid[x][y] = 1;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            dfs(grid, nx, ny);
        }
    }
};

1020. 飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例：

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

输出：3

解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

思路：

和上一题（1254）类似，也是求封闭岛屿，只是现在每块地都算一个岛屿了，我们也是从边界出发，最后遍历整个二维数组，看还剩几个1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int dx[4] = {0,0,1,-1};
    int dy[4] = {-1,1,0,0};
    int numEnclaves(vector<vector<int>>& grid) {
        //从边界开始dfs，然后把能去到的岛屿淹没，最后遍历剩余的1的个数即为答案
        int m = grid.size(), n = grid[0].size();
        for(int i = 0; i < n; i++){
            //从上面开始淹没
            dfs(grid, 0, i);
            //从下面开始淹没
            dfs(grid, m - 1, i);
        }
        for(int j = 0; j < m; j++){
            //从左边开始淹没
            dfs(grid, j, 0);
            //从右边开始淹没
            dfs(grid, j, n - 1);
        }
        int res = 0;
        //遍历输出 1 的个数
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    res++;
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int> >& grid, int x, int y){
        int m = grid.size(), n = grid[0].size();
        //base case
        if(x < 0 || y < 0 || x >= m || y >= n) return;
        if(grid[x][y] == 0) return;
        //把岛屿淹没
        grid[x][y] = 0;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            dfs(grid, nx, ny);
        }
    }
};

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

输出：6

解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

思路：

这题的⼤体思路和之前完全⼀样，只不过 dfs 函数淹没岛屿的同时，还应该想办法记录这个岛屿的⾯积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int> >& grid) {
        int m = grid.size(), n = grid[0].size();
        int res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    int ans = dfs(grid, i, j);
                    res = max(res, ans);
                }
            }
        }
        return res;
    }
    int dfs(vector<vector<int> >& grid, int x, int y){
        int m = grid.size(), n = grid[0].size();
        //base case
        if(x < 0 || y < 0 || x >= m || y >= n) return 0;
        if(grid[x][y] == 0) return 0;
        //淹没成水
        grid[x][y] = 0;
        return dfs(grid, x + 1, y)
             + dfs(grid, x, y + 1)
             + dfs(grid, x - 1, y)
             + dfs(grid, x, y - 1) + 1;
    }
};