☆打卡算法☆LeetCode 200. 岛屿数量算法解析

theme: arknights

携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第19天，点击查看活动详情

推荐阅读

CSDN主页
GitHub开源地址
Unity3D插件分享
简书地址
我的个人博客
QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个由 1陆地 0水组成的二维网格，计算网格中岛屿的数量。”

题目链接：

来源：力扣（LeetCode）

链接： 200. 岛屿数量 - 力扣（LeetCode）

2、题目描述

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

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

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

代码语言：javascript复制

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

代码语言：javascript复制

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

二、解题

1、思路分析

题意要计算网格中岛屿的数量。

为了求出网格中岛屿的数量，需要扫描整个二维网格，如果一个位置为1，将其加入到队列中，进行广度优先搜索BFS。

在广度优先搜索过程中，搜索到的1都会被标记为0，直到队列为空，搜索结束。

最终岛屿的数量，就是广度优先搜索的次数。

2、代码实现

代码参考：

代码语言：javascript复制

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;

        for (int r = 0; r < nr;   r) {
            for (int c = 0; c < nc;   c) {
                if (grid[r][c] == '1') {
                      num_islands;
                    grid[r][c] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    neighbors.add(r * nc   c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        if (row - 1 >= 0 &amp;&amp; grid[row-1][col] == '1') {
                            neighbors.add((row-1) * nc   col);
                            grid[row-1][col] = '0';
                        }
                        if (row   1 < nr &amp;&amp; grid[row 1][col] == '1') {
                            neighbors.add((row 1) * nc   col);
                            grid[row 1][col] = '0';
                        }
                        if (col - 1 >= 0 &amp;&amp; grid[row][col-1] == '1') {
                            neighbors.add(row * nc   col-1);
                            grid[row][col-1] = '0';
                        }
                        if (col   1 < nc &amp;&amp; grid[row][col 1] == '1') {
                            neighbors.add(row * nc   col 1);
                            grid[row][col 1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
}