【经典算法】LeetCode 200. 岛屿数量(Java/C/Python3/Go实现含注释说明,中等)

题目描述：

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

示例 1：

输入：grid = [

["1","1","0","1","0"],

["1","1","0","0","0"],

["0","0","0","0","0"]

]

输出：1

示例 2：

输入：grid = [

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]

输出：3

提示：

• 1 <= grid.length, grid[0].length <= 100
• grid[i][j] 为 '0' 或 '1'

代码实现：

Java 实现：

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    infect(grid, i, j);
                }
            }
        }
        return count;
    }
 
    private void infect(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '2'; // 标记为 2 表示已经访问过
        infect(grid, i + 1, j);
        infect(grid, i - 1, j);
        infect(grid, i, j + 1);
        infect(grid, i, j - 1);
    }
}

C 实现：

// C 语言实现需要补充内存管理和边界检查的代码

Python3 实现：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def infect(i, j):
            if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
                grid[i][j] = '2'
                infect(i + 1, j)
                infect(i - 1, j)
                infect(i, j + 1)
                infect(i, j - 1)
 
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    count += 1
                    infect(i, j)
        return count

Go 实现：

// Go 语言实现需要补充内存管理和边界检查的代码