目录

1. 题目描述

2. 方法一：广度优先搜索

2.1 思路

2.2 代码实现

3. 方法二：深度优先搜索

1. 题目描述

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

示例 2：

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

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 方法一：广度优先搜索

2.1 思路

        本质上就是找一个图中的连通子图的个数。 

        而连通性问题也可以看作是可到达性（reachability）问题。从某个格点出发，它所有到达的所有格点构成一个连通子图（从连通子图中的任何一点出发会得到同一结论）。

        既可以用深度优先搜索，也可以用广度优先优先搜索来解决。

        (1) 比如说从上到下逐行从左到右扫描找到的尚未访问过的第一个陆地格点

        (2) 从该格点出发通过广度或深度优先搜索，查找所有与它连通的陆地格点

        (3) 重复(1)-(2)直到所有陆地格点都被访问过

        grid数组中原始值为0或1，可以将访问过的陆地格点也置为0表示已经访问过，搜索任务不必关心某格点是原本就是0还是在访问后被置为0的。这样可以不必另行维护一个visited。当然以下代码中只判断陆地，所以只要修改为非“1”即可。

2.2 代码实现

from typing import List
from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid)==0 or len(grid[0])==0:
            return 0
        
        R,C       = len(grid),len(grid[0])
        islandCnt = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == "1":
                    # print(grid,r,c)
                    q = deque([(r,c)])
                    grid[r][c] = "0"
                    while len(q)>0:
                        (r0,c0) = q.popleft()
                        for x,y in [(r0-1,c0),(r0+1,c0),(r0,c0-1),(r0,c0+1)]:
                            if 0<=x<R and 0<=y<C and grid[x][y]=="1":
                                q.append((x,y))
                                grid[x][y] = "0"
                    islandCnt += 1
        return islandCnt

        执行用时：100 ms, 在所有 Python3 提交中击败了90.65%的用户

        内存消耗：23.7 MB, 在所有 Python3 提交中击败了84.57%的用户

3. 方法二：深度优先搜索

        本题用深度优先搜索也可以。反正都能遍历到整个图。

        看了看官解，居然还有第三种解法，叫做并查集。。。什么鬼，没听说过。。。^-^

        回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)