深/广度优先搜索示例-岛屿数量

卡码网链接：99. 岛屿数量

一、题目描述

二、代码

#dfs版本
def build_graph(): 
    n, m =  map(int,input().split())
    graph = []
    for row in range(n): 
        graph.append(list(map(int,input().split())))
    return graph,n,m 

def dfs(i,j,done_dict,graph):
    if graph[i][j] == 0 or done_dict[i][j] == 1: 
        return 
    done_dict[i][j] = 1
    for ii,jj in [[-1,0],[1,0],[0,-1],[0,1]]: 
        if i + ii >= 0 and i + ii < len(graph) and j+jj >=0 and j+jj < len(graph[0]):
            dfs(i+ii,j+jj,done_dict,graph)
    return 

def main(): 
    graph,rows,cols = build_graph() 
    done_dict = [[0 for _ in range(cols)] for _ in range(rows)] 
    resnum = 0 
    for i in range(rows):
        for j in range(cols):
            if graph[i][j] == 1 and done_dict[i][j] == 0:
                resnum += 1
                dfs(i,j,done_dict,graph) 
    return resnum 

if __name__ == "__main__":
    print(main())

#bfs版本
from collections import deque
def build_graph(): 
    n, m =  map(int,input().split())
    graph = []
    for row in range(n): 
        graph.append(list(map(int,input().split())))
    return graph,n,m 

def bfs(i,j,done_dict,graph):
    queue = deque([[i,j]])
    done_dict[i][j] = 1

    while len(queue):
        i,j = queue.popleft()
        add = [[-1,0],[1,0],[0,-1],[0,1]]
        for ii,jj in add:
            new_i = i+ii
            new_j = j+jj
            if new_i >= 0 and new_i < len(graph) and new_j >=0 and new_j < len(graph[0]) and graph[new_i][new_j] == 1 and done_dict[new_i][new_j] == 0: 
##############注意dfs时需要对next先赋已遍历的值，否则会大量重复搜索
                done_dict[new_i][new_j] = 1
                queue.append([new_i,new_j])
    return 

def main(): 
    graph,rows,cols = build_graph() 
    done_dict = [[0 for _ in range(cols)] for _ in range(rows)] 
    resnum = 0 
    for i in range(rows):
        for j in range(cols):
            if graph[i][j] == 1 and done_dict[i][j] == 0:
                resnum += 1
                bfs(i,j,done_dict,graph) 
    return resnum 

if __name__ == "__main__":
    print(main())