给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
#构造递归
def dfs(i, j):
#递归终止条件
if not 0<=i<len(grid) or not 0<=j<len(grid[0]) or grid[i][j] == '0':
return
grid[i][j] = '0'
#情况1
dfs(i+1,j)
#情况2
dfs(i-1,j)
#情况3
dfs(i,j+1)
#情况4
dfs(i,j-1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
#调用递归
dfs(i,j)
count += 1
#返回要优化的目标
return count