给你一个由 '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'
2. 题解
2.1 解法1:DFS递归方法
from typing import List
classSolution:defnumIslands(self, grid: List[List[str]])->int:ifnot grid ornot grid[0]:return0
m =len(grid)
n =len(grid[0])
ans =0for i inrange(m):for j inrange(n):if grid[i][j]=="1":
ans +=1
self.dfs(grid, m, n, i, j)return ans
defdfs(self, grid, m, n, r, c):
grid[r][c]="0"if r -1>=0and grid[r -1][c]=="1":
self.dfs(grid, m, n, r -1, c)if r +1< m and grid[r +1][c]=="1":
self.dfs(grid, m, n, r +1, c)if c -1>=0and grid[r][c -1]=="1":
self.dfs(grid, m, n, r, c -1)if c +1< n and grid[r][c +1]=="1":
self.dfs(grid, m, n, r, c +1)
2.2 解法2:DFS迭代方法
from typing import List
# DFS 迭代classSolution:defnumIslands(self, grid: List[List[str]])->int:ifnot grid ornot grid[0]:return0
m =len(grid)
n =len(grid[0])
ans =0for i inrange(m):for j inrange(n):if grid[i][j]=="1":print(i, j)
ans +=1
self.dfs(grid, m, n, i, j)return ans
defdfs(self, grid, m, n, row, col):
grid[row][col]="0"
stack =[[row, col]]while stack:
r, c = stack.pop()if r -1>=0and grid[r -1][c]=="1":
stack.append((r -1, c))
grid[r -1][c]="0"if r +1< m and grid[r +1][c]=="1":
stack.append((r +1, c))
grid[r +1][c]="0"if c -1>=0and grid[r][c -1]=="1":
stack.append((r, c -1))
grid[r][c -1]="0"if c +1< n and grid[r][c +1]=="1":
stack.append((r, c +1))
grid[r][c +1]="0"if __name__ =="__main__":
s = Solution()
grid =[["1","1","1"],["0","1","0"],["0","1","0"]]
a = s.numIslands(grid)print(a)
2.3 解法3:BFS迭代方法
from typing import List
from collections import deque
# BFS 迭代classSolution:defnumIslands(self, grid: List[List[str]])->int:ifnot grid ornot grid[0]:return0
m =len(grid)
n =len(grid[0])
ans =0
queue = deque()for i inrange(m):for j inrange(n):if grid[i][j]=="1":
ans +=1
queue.append((i, j))whilelen(queue)>0:
top = queue.popleft()
r, c = top[0], top[1]if r -1>=0and grid[r -1][c]=="1":
queue.append((r -1, c))
grid[r -1][c]="0"if r +1< m and grid[r +1][c]=="1":
queue.append((r +1, c))
grid[r +1][c]="0"if c -1>=0and grid[r][c -1]=="1":
queue.append((r, c -1))
grid[r][c -1]="0"if c +1< n and grid[r][c +1]=="1":
queue.append((r, c +1))
grid[r][c +1]="0"return ans
if __name__ =="__main__":
s = Solution()
grid =[["1","1","1"],["0","1","0"],["0","1","0"]]
a = s.numIslands(grid)print(a)