3.1.3 DFS 算法解决岛屿问题

问题一、岛屿数量

题目会输入一个二维数组 grid，其中包含 0 或者 1，0 代表海水，1 代表陆地，且假设该矩阵四周都是被海水包围着。
连接片的陆地形成岛屿，写一个算法计算矩阵 grid 中岛屿个数，函数签名如下：

关键在于如何寻找并标记「岛屿」，代码如下：

// 从（i, j） 开始，将与之相邻的陆地都变成海水
void dfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超过索引边界
        return;
    }
    if (grid[i][j] == '0') {
        // 已经是海水了
        return;
    }
    // 将（i, j） 变成海水
    grid[i][j] = '0';
    // 淹没上下左右的陆地
    dfs(grid, i - 1, j);
    dfs(grid, i + 1, j);
    dfs(grid, i, j - 1);
    dfs(grid, i, j + 1);
}
// 主函数
int numIslands(vector<vector<char>>& grid) {
    int res = 0;
    int m = grid.size(), n = grid[0].size();
    // 遍历 grid
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '1') {
                // 每发现一个岛屿，岛屿数量+1
                res++;
                // 然后使用 DFS 将岛屿淹没
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

每次遇到岛屿，都要用 DFS 算法将岛屿「淹没」，避免维护 visited 数组。因为 DFS 函数遍历到值为 0 的位置都会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。
使用 visited 数组代码入下：

void dfs(vector<vector<char>>& grid, int i, int j, vector<vector<bool>>& visited) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 越界
        return;
    }
    if (grid[i][j] == '0') {
        // 本身就是海水
        return;
    }
    if (visited[i][j] == true) {
        // 遍历过了
        return;
    }
    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);
}
int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) {
        return 0;
    }
    int m = grid.size(), n = grid[0].size();
    int res = 0;
    vector<vector<bool>> visited(m, vector<bool>(n));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                res++;
                // visited[i][j] = true;
                dfs(grid, i, j, visited);
            }
        }
    }
    return res;
}

问题二、封闭岛屿数量

上一题说二维矩阵四周可以认为也是被海水包围的，所以靠边的陆地也算岛屿。
对于封闭岛屿的数量来说和上一题不同：

• 用 0 表示陆地，用 1 表示海水；
• 计算「封闭岛屿」的数目。「封闭岛屿」就是上下左右全部被 1 包围的 0，也就是说靠边的陆地并不算「封闭岛屿」

函数签名如下：

如何判断「封闭岛屿」？把上一题中那些靠边的岛屿排除掉，剩下的就是「封闭岛屿」。

void dfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || j < 0 || i >= m || j >= n) {
        return;
    }
    if (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);
}
int closedIsland(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();

    for (int j = 0; j < n; ++j) {
        // 将靠上边的岛屿淹没掉
        dfs(grid, 0, j);
        // 将靠下边的岛屿淹没掉
        dfs(grid, m - 1, j);
    }
    for (int i = 0; i < m; ++i) {
        // 将靠左边的岛屿淹没掉
        dfs(grid, i, 0);
        // 把靠右边的岛屿淹没掉
        dfs(grid, i, n - 1);
    }

    // 遍历 grid，剩下的都是封闭岛屿
    int res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 0) {
                res++;
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

问题三、飞地的数量

翻译一下题目：这题不求封闭岛屿的数量，而是求封闭岛屿的面积总和。思路相同，先把靠边的陆地淹掉，然后数剩下的陆地数量即可。

void dfs(vector<vector<int>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || i >= m || j < 0 || j >= n) {
        return;
    }
    if (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);
}
int numEnclaves(vector<vector<int>>& grid) {
    if (grid.empty()) {
        return 0;
    }
    // 淹掉靠边的陆地
    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 i = 0; i < m; ++i) {
        dfs(grid, i, 0);
        dfs(grid, i, n - 1);
    }

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

问题四、岛屿的最大面积

0 表示海水，1 表示陆地，不计算岛屿的个数，让计算最大的那个岛屿的面积。函数签名如下：

可以给 DFS 函数设置返回值，记录每次淹没的陆地个数。代码如下：

int dfs(vector<vector<int>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || i >= m || j < 0 || j >= n) {
        return 0;
    }
    if (grid[i][j] == 0) {
        return 0;
    }
    grid[i][j] = 0;
    return dfs(grid, i - 1, j) + 
            dfs (grid, i + 1, j) +
            dfs(grid, i, j - 1) +
            dfs(grid, i, j + 1) + 1;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
    if (grid.empty()) {
        return 0;
    }
    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 = max(res, dfs(grid, i, j));
            }
        }
    }
    return res;
}

问题五、子岛屿的数量

这道题的关键在于，如何快速判断子岛屿？什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛屿？
当岛屿 B 中所有的陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛屿。
反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。
代码如下：

void dfs(vector<vector<int>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || j < 0 || i >= m || j >= n) {
        return;
    }
    if (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);
}

int countSubIslands(vector<vector<int>>& grip1, vector<vector<int>>& grip2) {
    if (grip1.empty()) {
        return 0;
    }
    int m = grip1.size(), n = grip1[0].size();
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grip1[i][j] == 0 && grip2[i][j] == 1) {
                // 这个岛屿一定不是子岛，淹掉
                dfs(grip2, i, j);
            }
        }
    }
    // 现在 grip2 中剩下的岛屿都是子岛，计算岛屿数量
    int res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grip2[i][j] == 1) {
                res++;
                dfs(grip2, i, j);
            }
        }
    }
    return res;
}

问题六、不同的岛屿数量

题目输入还是一个二维矩阵，0 表示海水，1 表示陆地，计算不同岛屿的数量。函数签名如下：

比如输入下面的矩阵：

其中有四个岛屿，但是左下角和右上角的岛屿形状相同，所以不同岛屿数量共有三个，算法返回 3。
显然需要先将二维矩阵中的「岛屿」进行转化，变成比如字符串这样的类型，然后利用 Set 这样的数据结构去重，最终得到不同岛屿的个数。
将岛屿转换为字符串，就是序列化。
首先，对于形状相同的岛屿，如果从同一起点出发，DFS 函数遍历的顺序肯定是一样的。
因为遍历顺序是写死在递归函数里面的，不会动态变化：
所以，遍历顺序从某种意义来说可以用来描述岛屿的形状，比如下图的两个岛屿：

假设遍历的顺序是：

分别用1, 2, 3, 4 代表上、下、左、右，用 -1， -2， -3， -4 代表上下左右的撤销，那么可以这样表示它们的遍历顺序：

这就相当于岛屿序列化的结果，只要每次使用 DFS 遍历岛屿的时候生成这串数字进行比较，就可以计算到底有多少个不同的岛屿了。需要修改 dfs 函数，添加一些函数记录遍历顺序：

void dfs(vector<vector<int>>& grid, int i, int j, string& str, int dir) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
        return;
    }
    // 前序遍历位置：进入（i, j）
    grid[i][j] = 0;
    str.append(to_string(dir)).append(",");
    dfs(grid, i - 1, j, str, 1);    // 上
    dfs(grid, i + 1, j, str, 2);    // 小
    dfs(grid, i, j - 1, str, 3);    // 左
    dfs(grid, i, j + 1, str, 4);    // 右
    // 后序遍历位置：离开（i, j）
    str.append(to_string(-dir)).append(",");
}

dir 记录方向，dfs 函数递归结束后，str 记录着整个遍历顺序。
主函数如下：

int numDistinctIslands(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    set<string> islands;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1) {
                // 淹掉这个岛屿，同时存储岛屿序列化的结果
                string str = "";
                // 初始化方向不影响正确性
                dfs(grid, i, j, str, -1);
                islands.insert(str);
            }
        }
    }
    return islands.size();
}