Leetcode 200 题 岛屿数量

题目描述

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

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

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

示例 ：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3

思路分析

这道题需要我们求出岛屿的数量，一个岛屿，由一片相邻的 '1' 组成，这道题我们可以通过搜索，把岛屿所包含的所有 '1' 都找出来。

对于某一个岛屿，即二维表中的某一个格子，我们需要去看它上下左右相邻的格子，如果某个格子为 '0'，说明是边界，我们不需要管它，如果我们搜索到的某个格子是 '1'，那么我们就又得要以这个格子为起点，搜索它的上下左右。为了防止重复设置起点，我们可以将已经搜索到的 '1' 设置为 '0'。

我们从第一个格子开始遍历，找到第一个 '1'，直至找到所有与之相连的 '1'。

image.png

找到 '1' 后为了防止重复重复搜索，我们需要把找到的 '1' 全部置为 '0'。

image.png

我们继续遍历，将会找到第二个 '1'，我们按照上面的方法找到所有与之相邻的 '1'，并把它们置为 '0'。

image.png

直到最后，我们会把所有整个二维矩阵的值都变为 '0'，这其间，我们通过 '1' 这个入口找到岛屿三次，因此，岛屿数量为3。

代码描述

下面使用 Java 进行代码描述：
这里使用 offsetx 和 offsety 来保存偏移量，方便对格子上下左右的处理。

class Solution {
    int offsetx[] = {1, 0, -1, 0};
    int offsety[] = {0, 1, 0, -1};
    public int numIslands(char[][] grid) {
        int num = 0; // 岛屿数量

        int m = grid.length;
        int n = grid[0].length;

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

        return num;
    }

    public void dfs(char[][] grid, int x, int y) {
        // 将当前状态改为 0
        grid[x][y] = '0';

        // 遍历上下左右
        for (int i = 0; i < 4; i++) {
            int nx = x + offsetx[i];
            int ny = y + offsety[i];
            if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length)
                continue;
            if (grid[nx][ny] == '1') {
                dfs(grid, nx, ny);
            }
        }

    }
}

欢迎关注

技术公众号：【小猿君的算法笔记】
一起学习，一起成长。