岛屿数量

一、题目描述

给你一个由 '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

二、题目解析

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
class Solution {
    public int numIslands(char[][] grid) {

        // count 代表岛屿数量
        int count = 0;

        // mark 标记已经搜索的位置,大小与 grid 一致
        int[][] mark = new int[grid.length][grid[0].length];

        // mark 初始化为 0
        for(int[] c : mark) {
           Arrays.fill(c, 0);
        }

        // 遍历 grid
        for(int i = 0 ; i < grid.length ; i++){
            for(int j = 0 ; j < grid[i].length;j++){

                // 如果发现位置 (i ,j)是没有标记的陆地
                if(mark[i][j] == 0 && grid[i][j] == '1'){
                    // 对该位置进行搜索
                    DFS(grid,i,j,mark);
                    // 对 (i ,j)完成搜索后,岛屿数量加 1
                    count++;
                }
            }
        }

        return count;

    }

    // 将 grid 中与 x ,y 相连的位置在 mark 中进行标记
    private void DFS(char[][] grid, int x, int y,int[][] mark) {

        // 当前搜索位置在 mark 中标记为 1 ,代表已经遍历了
        mark[x][y] = 1;

        // dx 为行的方向数组
        int dx[] = { -1 , 1 , 0 , 0 };

        // dy 为行的方向数组
        int dy[] = { 0 , 0 , -1 , 1 };

        // 循环遍历当前位置的上、下、左、右四个方向
        for( int i = 0 ; i < 4 ; i++){

            // newX 代表新的行
            int newX = dx[i] + x;

            // newY 代表新的列
            int newY = dy[i] + y;

            // 如果新的位置超出了数组边界
            if(newX < 0 || newX >= mark.length || newY < 0 || newY >= mark[newX].length){
                // 跳出该位置
                continue;
            }

            // 如果发现新位置是陆地,并且没有被标记过
            if(grid[newX][newY] == '1' && mark[newX][newY] == 0){
                // 递归搜索新的位置
                DFS(grid,newX,newY,mark);
            }


        }

    }
}

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注