图论 | 岛屿数量（深搜，广搜）

岛屿数量

acm模式：99.岛屿数量 核心代码模式： 200. 岛屿数量

思路

dfs

def dfs(grid,i,j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]):
return
if grid[i][j] == 0:
return
else:
grid[i][j] = 0
dfs(grid,i–1,j)
dfs(grid,i+1,j)
dfs(grid,i,j–1)
dfs(grid,i,j+1)

def main():
# 构造岛屿
n,m = map(int,input().split())
grid = []
for _ in range(n):
grid.append(list(map(int,input().split())))

res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
res = res+1
dfs(grid,i,j)
print(res)

if __name__ == "__main__":
main()

bfs

from collections import deque

def bfs(grid,i,j):
queue = deque([(i,j)])
while queue:
i,j = queue.popleft()
if i>=0 and i<len(grid) and j>=0 and j<len(grid[0]) and grid[i][j]==1:
grid[i][j] = 0
queue.append((i–1,j))
queue.append((i+1,j))
queue.append((i,j–1))
queue.append((i,j+1))

def main():
# 构造岛屿
n,m = map(int,input().split())
grid = []
for _ in range(n):
grid.append(list(map(int,input().split())))

res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
res = res+1
bfs(grid,i,j)
print(res)

if __name__ == "__main__":
main()