LeetCode 200、岛屿数量

一、题目描述

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

二、题目解析

三、参考代码

1、Java 代码

// 登录 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);
            }


        }

    }
}

**2、**C++ 代码

3、Python 代码

登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 岛屿数量（ LeetCode 200 ）:https://leetcode-cn.com/problems/number-of-islands/submissions/
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        # count 代表岛屿数量
        count = 0

        # mark 标记已经搜索的位置，大小与 grid 一致
        # mark 初始化为 0
        mark = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]

    
        # 遍历 grid
        for i in range(len(grid)):
            for j in range(len(grid[i])):

                # 如果发现位置 （i ，j）是没有标记的陆地
                if mark[i][j] == 0 and grid[i][j] == "1":
                    # 对该位置进行搜索
                    self.DFS(grid,i,j,mark)
                    # 对 （i ，j）完成搜索后，岛屿数量加 1
                    count += 1

        return count


    # 将 grid 中与 x ，y 相连的位置在 mark 中进行标记
    def DFS(self,grid,x,y,mark: List[List[str]]) :

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

        # 循环遍历当前位置的上、下、左、右四个方向
        for dx, dy in ((0,1), (1,0), (0,-1), (-1,0)):

            # newX 代表新的行
            newX = dx + x

            # newY 代表新的列
            newY = dy + y

            # 如果新的位置超出了数组边界
            if newX < 0 or newX >= len(mark) or newY < 0 or newY >= len(mark[newX]) : 
                # 跳出该位置
                continue

            # 如果发现新位置是陆地，并且没有被标记过
            if grid[newX][newY] == "1" and mark[newX][newY] == 0 :
                # 递归搜索新的位置
                self.DFS(grid,newX,newY,mark)