島嶼數量

acm模式：99.島嶼數量
核心代碼模式： 200. 島嶼數量

思路

1. 遍歷grid，如果它是1，則通過bfs/dfs將這個小島的grid變為0

dfs

def dfs(grid,i,j):if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]):returnif grid[i][j] == 0:returnelse:grid[i][j] = 0dfs(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 = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:res = res+1dfs(grid,i,j)print(res)if __name__ == "__main__":main()  

bfs

from collections import dequedef 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] = 0queue.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 = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:res = res+1bfs(grid,i,j)print(res)if __name__ == "__main__":main()