200. 岛屿数量
Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
代码语言：javascript复制Input:
11110
11010
11000
00000
Output: 1Example 2:
代码语言：javascript复制Input:
11000
11000
00100
00011
Output: 3Solution-DFS
代码语言：javascript复制class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
row = len(grid)
col = len(grid[0]) if row else 0
if not row or not col: return 0
res = 0
def dfs(i,j):
grid[i][j] = 0
for x,y in [(0,1),(0,-1),(1,0),(-1,0)]:
if 0<=i x<row and 0<=j y<col and grid[i x][j y]=="1":
dfs(i x,j y)
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
dfs(i,j)
res = 1
return resSolution-BFS
代码语言：javascript复制class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
row = len(grid)
col = len(grid[0]) if row else 0
if not row or not col: return 0
res = 0
def bfs(i,j):
grid[i][j] == "0"
q = [(i,j)]
while q:
i,j = q.pop()
for x,y in [(0,1),(0,-1),(1,0),(-1,0)]:
if 0<=i x<row and 0<=j y<col and grid[i x][j y]=="1":
q.append((i x,j y))
grid[i x][j y] = "0"
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
bfs(i,j)
res = 1
return resSolution-UF
代码语言：javascript复制class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
row = len(grid)
col = len(grid[0]) if row else 0
if not row or not col: return 0
dummy_node = row*col
uf = UnionFind(dummy_node 1)
for i in range(row):
for j in range(col):
if grid[i][j] == "0":
uf.Union(dummy_node, i*col j)
if grid[i][j] == "1":
for x,y in [(0,1), (1,0)]:
if i x<row and j y<col and grid[i x][j y] == '1':
uf.Union((i x)*col (j y), (i*col) j)
return uf.Count()-1UnionFind Class
并查集(Union-Find)算法介绍 link
并查集（参考leetcode323题）link
代码语言：javascript复制class UnionFind:
def __init__(self, n):
self.count = n
self.parent = [i for i in range(n)]
def Find(self, p):
while p != self.parent[p]:
self.parent[p] = self.parent[self.parent[p]]
p = self.parent[p]
return self.parent[p]
def Union(self, p, q):
p_root = self.Find(p)
q_root = self.Find(q)
self.parent[p_root] = q_root
self.count -= 1
def Count(self):
return self.count
def is_connected(self, p, q):
return self.Find(p) == self.Find(q)
