题目描述：

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

解题思路一：bfs，主要思想都是遇到一个没有visited过的"陆地"先result += 1，然后用深搜或者广搜将这片"陆地"全部做上visited标记。

class Solution:def __init__(self):self.dirs = [(-1,0), (0, 1), (1, 0), (0, -1)] # 左上右下def numIslands(self, grid: List[List[str]]) -> int:m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]result = 0for i in range(m):for j in range(n):if not visited[i][j] and grid[i][j] == '1':result += 1self.bfs(grid, i, j, visited)return resultdef bfs(self, grid, x, y, visited):q = deque()q.append((x, y))visited[x][y] = Truewhile q:x, y = q.popleft()for d in self.dirs:nextx = x + d[0]nexty = y + d[1]if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):continueif not visited[nextx][nexty] and grid[nextx][nexty] == '1':q.append((nextx, nexty))visited[nextx][nexty] = True

时间复杂度：O(nm)
空间复杂度：O(nm)

解题思路二：dfs

class Solution:def numIslands(self, grid: List[List[str]]) -> int:m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]dirs = [(-1,0), (0, 1), (1, 0), (0, -1)] # 左上右下result = 0def dfs(x, y):for d in dirs:nextx = x + d[0]nexty = y + d[1]if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:continueif not visited[nextx][nexty] and grid[nextx][nexty] == '1':visited[nextx][nexty] = Truedfs(nextx, nexty)for i in range(m):for j in range(n):if not visited[i][j] and grid[i][j] == '1':visited[i][j] = Trueresult += 1dfs(i, j)return result

时间复杂度：O(nm)
空间复杂度：O(nm)

解题思路三：并查集

class Solution:def numIslands(self, grid: List[List[str]]) -> int:f = {}def find(x):f.setdefault(x, x)if f[x] != x:f[x] = find(f[x])return f[x]def union(x, y):f[find(x)] = find(y)if not grid: return 0row = len(grid)col = len(grid[0])for i in range(row):for j in range(col):if grid[i][j] == "1":for x, y in [[-1, 0], [0, -1]]:tmp_i = i + xtmp_j = j + yif 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":union(tmp_i * row + tmp_j, i * row + j)# print(f)res = set()for i in range(row):for j in range(col):if grid[i][j] == "1":res.add(find((i * row + j)))return len(res)

时间复杂度：O(mn)
空间复杂度：O(nm)