算法-双指针、BFS与图论-1101. 献给阿尔吉侬的花束-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法-双指针、BFS与图论-1101. 献给阿尔吉侬的花束。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

算法-双指针、BFS与图论-1101. 献给阿尔吉侬的花束,算法设计与分析,宽度优先,图论,算法文章来源地址https://www.toymoban.com/news/detail-839653.html

思路

BFS可以搜环，有环也没有关系，如果有解：一定可以找到一条最小步数的合法的路径
Python中 collections模块的详细用法介绍_python collections-CSDN博客
引用自上述文章：

append(x)：添加 x 到右端。

appendleft(x)：添加 x 到左端。

clear()：移除所有元素，使其长度为0.

copy()：创建一份浅拷贝。3.5 新版功能.

count(x)：计算deque中个数等于 x 的元素。3.2 新版功能.

extend(iterable)：扩展deque的右侧，通过添加iterable参数中的元素。

extendleft(iterable)：扩展deque的左侧，通过添加iterable参数中的元素。注意，左添加时，在结果中iterable参数中的顺序将被反过来添加。

index(x[, start[, stop]])：返回第 x 个元素（从 start 开始计算，在 stop 之前）。返回第一个匹配，如果没找到的话，升起 ValueError 。3.5 新版功能.

insert(i, x)：在位置 i 插入 x 。如果插入会导致一个限长deque超出长度 maxlen 的话，就升起一个 IndexError 。3.5 新版功能.

pop()：移去并且返回一个元素，deque最右侧的那一个。如果没有元素的话，就升起 IndexError 索引错误。

popleft()：移去并且返回一个元素，deque最左侧的那一个。如果没有元素的话，就升起 IndexError 索引错误。

remove(value)：移去找到的第一个 value。如果没有的话就升起 ValueError 。

reverse()：将deque逆序排列。返回 None 。3.2 新版功能.

rotate(n=1)：向右循环移动 n 步。如果 n 是负数，就向左循环。如果deque不是空的，向右循环移动一步就等价于 d.appendleft(d.pop()) ，向左循环一步就等价于 d.append(d.popleft()) 。

Deque对象同样提供了一个只读属性:
maxlen：Deque的最大尺寸，如果没有限定的话就是 None 。

代码

from collections import deque  # 导入deque模块，用于实现队列数据结构

dx = [-1, 0, 1, 0]  # 定义x方向的偏移量，分别表示上、右、下、左
dy = [0, 1, 0, -1]  # 定义y方向的偏移量，分别表示上、右、下、左

def bfs(start, end):
    # 初始化距离数组为-1，表示未访问过
    dist = [[-1] * m for _ in range(n)]
    # 起点到自身的距离为0
    dist[start[0]][start[1]] = 0

    # 使用deque实现队列，初始将起点加入队列中
    q = deque([start])

    # BFS搜索过程
    while q:
        # 取出队列中的第一个元素
        t = q.popleft()

        # 遍历当前位置的四个邻居节点
        for i in range(4):
            a, b = t[0] + dx[i], t[1] + dy[i]

            # 如果邻居节点越界或者已经访问过，跳过当前循环
            if a < 0 or a >= n or b < 0 or b >= m:
                continue
            if dist[a][b] != -1: # 说明可以走
                continue
            # 如果邻居节点是障碍物，跳过当前循环
            if g[a][b] == '#':
                continue

            # 更新邻居节点的距离，并加入队列中
            dist[a][b] = dist[t[0]][t[1]] + 1

            # 如果邻居节点是终点，返回最短路径长度
            if (a, b) == end:
                return dist[a][b]

            q.append((a, b))

    # 如果无法到达终点，返回-1
    return -1

# 读取测试样例数量
T = int(input())

# 遍历每个测试样例
for _ in range(T):
    # 读取迷宫的行数和列数
    n, m = map(int, input().split())

    # 读取迷宫的每一行
    g = [input() for _ in range(n)] # 读入的是字符串

    start, end = None, None
    # 查找起点和终点的位置
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'S':
                start = (i, j) # 元组
            elif g[i][j] == 'E':
                end = (i, j)

    # 使用BFS计算最短路径长度，并打印结果
    distance = bfs(start, end)

    if distance == -1:
        print("oop!")
    else:
        print(distance)

到了这里，关于算法-双指针、BFS与图论-1101. 献给阿尔吉侬的花束的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！