【图论】200. 岛屿问题

200. 岛屿问题

难度：中等
力扣地址：https://leetcode.cn/studyplan/top-100-liked/

问题描述

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

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

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

示例 1：

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1

示例 2：

输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

问题分析

有没有小伙伴跟我一样，这类题目一看就想尝试一下深度优先遍历 DFS ？

DFS 写起来比较简单，也比较容易理解，所以真心推荐合适场景下考虑 DFS。

如下图所示，白色筷子表示 “水”，也就是遍历时的边界。

所以接下的问题就非常简单，我们从 (0, 0) 这个坐标出发，如果是陆地就 travel，也就是 DFS 遍历，如果是水，就修改方向，如果没有地方去了，就切换到下一个陆地。

（为了更好理解，我们可以考虑：把经过的陆地，全部都换成水，避免下次还来这个地方）

解题代码

对应的 C++ 代码如下：

class Solution {
public:
    void travel(vector<vector<char>>& grid, int x, int y) {
        // 遇到边界或没有可访问的点
        if (x >= grid.size() || x < 0 || y >= grid[0].size() || y < 0 || grid[x][y] == '0') {
            return;
        }
        // 标记一下已经访问
        grid[x][y] = '0';
        // 四个方向 travel
        travel(grid, x + 1, y);
        travel(grid, x - 1, y);
        travel(grid, x, y + 1);
        travel(grid, x, y - 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        // 记录结果
        int result = 0;

        // 根据 (i, j) 开始尝试 travel
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                // 如果遇到的这个点是陆地
                if (grid[i][j] == '1') {
                    // 开始travel
                    travel(grid, i, j);
                    // travel 结束后 + 1，表示那一片陆地已经访问过了
                    result += 1;
                }
            }
        }
        return result;
    }
};

• 时间复杂度：O(MN)
• 空间复杂度：O(MN）

对应的 java 代码如下：

class Solution {
    // 定义 travel 方法
    public void travel(char[][] grid, int x, int y) {
        // 遇到边界或没有可访问的点
        if (x >= grid.length || x < 0 || y >= grid[0].length || y < 0 || grid[x][y] == '0') {
            return;
        }
        // 标记已经访问过的点
        grid[x][y] = '0';
        // 四个方向进行递归调用
        travel(grid, x + 1, y);
        travel(grid, x - 1, y);
        travel(grid, x, y + 1);
        travel(grid, x, y - 1);
    }

    // 定义 numIslands 方法
    public int numIslands(char[][] grid) {
        // 记录结果
        int result = 0;

        // 遍历整个网格
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 如果遇到陆地
                if (grid[i][j] == '1') {
                    // 开始进行递归访问
                    travel(grid, i, j);
                    // 访问结束后计数加一
                    result++;
                }
            }
        }
        // 返回结果
        return result;
    }
}

对应的python代码为

class Solution:
    def travel(self, grid, x, y):
        # 遇到边界或没有可访问的点
        if x >= len(grid) or x < 0 or y >= len(grid[0]) or y < 0 or grid[x][y] == '0':
            return
        # 标记已经访问过的点
        grid[x][y] = '0'
        # 四个方向进行递归调用
        self.travel(grid, x + 1, y)
        self.travel(grid, x - 1, y)
        self.travel(grid, x, y + 1)
        self.travel(grid, x, y - 1)

    def numIslands(self, grid):
        # 记录结果
        result = 0

        # 遍历整个网格
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # 如果遇到陆地
                if grid[i][j] == '1':
                    # 开始进行递归访问
                    self.travel(grid, i, j)
                    # 访问结束后计数加一
                    result += 1
        # 返回结果
        return result

总结

作为 DFS 的一个比较简单的例子，限制条件也比较少，只需要考虑边界问题即可。先应该学习一下 DFS 的基本逻辑，然后能够写 DFS 的代码，在此基础上稍微改改就可以刷这道题。

我更加想称这个操作为防水游戏，就是把每块岛屿都用海水淹没，看看需要操作多少次。

多谢小伙伴们的点赞支持 ~

Smileyan
2024.06.30 23:52