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

岛屿数量

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]):
        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()