题目-中等难度
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例
示例 1：
示例 2：
提示：
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1. dfs
时间
108ms
击败 78.12%使用 Python3 的用户
内存
25.87MB
击败 72.49%使用 Python3 的用户
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 获取网格长宽
lg,lgg = len(grid),len(grid[0])
# 递归填充网格内为1的项
def dfs(grid,x,y):
# 确保x,y在网格中, 并且当前网格值为1
if (0<=x<lg and 0<=y<lgg and grid[x][y]=='1'):
# 将网格变化为0
grid[x][y] = '0'
# 对相邻网格为1的进行填充
dfs(grid,x+1,y)
dfs(grid,x-1,y)
dfs(grid,x,y+1)
dfs(grid,x,y-1)
# 计数
c = 0
# 遍历网格
for m in range(lg):
for n in range(lgg):
# 若当前网格值为1
if grid[m][n] == '1':
# 递归填充
dfs(grid,m,n)
# 计数+1
c+=1
# 返回计数
return c
2. bfs
时间
112ms
击败 70.03%使用 Python3 的用户
内存
25.75MB
击败 88.17%使用 Python3 的用户
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 获取网格长宽
lg,lgg = len(grid),len(grid[0])
# 计算
res = 0
# 遍历网格
for i in range(lg):
for j in range(lgg):
# 如果网格值为1
if grid[i][j] == '1':
# 添加至li列表开始广度优先搜索
li = [(i,j)]
while li:
# 获取当前网格
x,y = li.pop(0)
# 由于广度优先会存在一种情况,如li列表中的网格已经将'1'变为'0'的情况, 所以需要跳过
if grid[x][y] == '0':
continue
# 将当前网格值替换为0
grid[x][y] = '0'
# 对网格进行搜索
for xx,yy in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
if 0<=xx<lg and 0<=yy<lgg and grid[xx][yy] == '1':
li.append((xx,yy))
res += 1
return res