算盘 - 广优搜

走迷宫最笨的一种方法是右手摸墙, 实际上是一种深度优先搜索(DFS). 对于迷宫树来说, DFS会一路走到叶子节点返回. 广度优先搜索不一样, 对于当前节点可以访问到的全部子节点都会入队, 叶子节点返回.

广度优先搜索

队列

队列先进先出的数据结构, Python实现比较简单.

queue = []

# 入队
e = 1
queue.append(e)

# 出队
queue.pop(0)

搜索

    queue = [frist]
    while len(queue) != 0:
        _ = queue.pop(0)

岛屿数量

• 题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

输入:
11110
11010
11000
00000

输出: 1

• 解法

定义岛屿

maps = [
    [1, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 0, 0, 0],
    [1, 0, 0, 0],
]

初始化 visited visited = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]. 遍历 maps, bfs.

def s():
    ans = 0
    for y in range(len(maps)):
        for x in range(len(maps[0])):
            if maps[y][x] == 1 and visited[y][x] == False:
                bfs(y, x)
                visited[y][x] = True
                ans += 1
            elif visited[y][x] == False:
                visited[y][x] = True
    print(ans)

bfs

def bfs(y, x):
    queue = [(y, x)]
    while len(queue) != 0:
        pos = queue.pop(0) # 出队
        if 0 <= pos[0]+1 < len(maps) and 0 <= pos[1] < len(maps[0]) and not visited[pos[0]+1][pos[1]] and maps[pos[0]+1][pos[1]] == 1:
            queue.append((pos[0]+1, pos[1])) # 入队
        if 0 <= pos[0]-1 < len(maps) and 0 <= pos[1] < len(maps[0]) and not visited[pos[0]-1][pos[1]] and maps[pos[0]-1][pos[1]] == 1:
            queue.append((pos[0]-1, pos[1]))
        if 0 <= pos[0] < len(maps) and 0 <= pos[1]+1 < len(maps[0]) and not visited[pos[0]][pos[1]+1] and maps[pos[0]][pos[1]+1] == 1:
            queue.append((pos[0], pos[1]+1))
        if 0 <= pos[0] < len(maps) and 0 <= pos[1]-1 < len(maps[0]) and not visited[pos[0]][pos[1]-1] and maps[pos[0]][pos[1]-1] == 1:
            queue.append((pos[0], pos[1]-1))
        visited[pos[0]][pos[1]] = True