本文共 1540 字，大约阅读时间需要 5 分钟。

蓝桥杯是国内最具影响力的高中生计算机竞赛之一，它不仅是一个展示编程能力的平台，更是许多学生开启技术之路的起点。对于打算参加蓝桥杯的同学，博主的博客无疑是一个值得关注的资源，正在准备的蓝桥杯题目也值得大家跟着博客一起刷题。

BFS 算法

在编程竞赛中，广度优先搜索（BFS）是一种核心算法，常用于解决路径寻找、最短路径等问题。与深度优先搜索（DFS）不同，BFS采用队列结构，按照层序遍历的方式逐层扩展节点。以下是 BFS 的基本概念和实现方法。

BFS 的实现原理

队列：BFS 使用队列来管理待处理的节点。

初始状态：将起点加入队列。

遍历过程：

• 取出队列首元素（通常使用队首元素）。
• 展开当前节点，生成新节点。
• 对每个新节点进行判重（防止重复访问），若未被访问过则加入队列。

终止条件：当队列为空时，搜索完成。

队列的特点决定了 BFS 是层序遍历，最适合寻找最短路径问题。下图展示了 BFS 的典型队列操作过程：

队列: [起点]
取出起点，生成所有未访问的新节点，入队。
队列: [新节点1, 新节点2, ...]
继续循环，直到找到目标节点或队列为空。

BFS 的实现模板

判重数组：用于记录已访问节点。

队列：用于管理当前层的节点。

伪代码模板：

queue ← 初始状态
while (queue非空):
    t ← 队首
    for (拓展t):
        ver ← 新节点
        if (!st[ver]):
            ver → 队尾

示例与应用

第一个样例：需要走5步，答案为5。

第三个样例：被墙阻挡，无法吃到奶酪，输出“oop!”。 这些例子展示了 BFS 在实际问题中的广泛应用，特别是在图形路径问题中，BFS 能够有效找到最短路径。

Flood Fill 算法

Flood Fill（洪水灌溉）算法是一种填充算法，常用于图形处理。其核心思想是从起点开始，逐层扩展，类似于 BFS。以下是 Flood Fill 的实现思路：

初始状态：将起点加入队列，并标记为已访问。

遍历过程：

• 取出队列首元素。
• 展开当前节点，生成所有相邻的新节点。
• 对每个新节点进行判重（防止重复访问），若未被访问过，则加入队列。

终止条件：当队列为空时，算法结束。

Flood Fill 的典型应用是计算图形中的连通块数量。例如，给定一个由“#”和“.”组成的网格，Flood Fill 可以帮助统计连通的“.”区域数量。

BFS 在三维空间中的应用

在二维空间中，BFS 使用4个方向偏移量进行扩展。在三维空间中，方向偏移量增加到6个方向（上、下、前、后、左、右）。以下是三维 BFS 的实现思路：

初始状态：将起点加入队列。

遍历过程：

• 取出队列首元素。
• 展开当前节点，生成所有相邻的新节点。
• 对每个新节点进行判重（防止重复访问），若未被访问过，则加入队列。

终止条件：当队列为空时，搜索完成。

BFS 在三维空间中的适用性同样显著，能够有效解决路径寻找和最短路径问题。

第九届2018年蓝桥杯真题

JavaB组第9题：求会被完全淹没的岛屿数量。

问题描述：给定一个由“#”、“.”和“S”、“E”组成的地图，S为起点，E为终点。某些岛屿会因为与海相连而被完全淹没。我们需要计算被完全淹没的岛屿数量。

解决方法：

使用 BFS 计算连通块数量。

统计与海相连的岛屿数量。

比较连通块数量与边界数量，若相等则表示该岛屿会被完全淹没。

总结

BFS 是解决路径问题的核心算法，其简单易懂的实现方式使其在编程竞赛中广泛应用。从二维到三维空间，BFS 的思想不变，仅需根据空间维度调整方向偏移量即可。希望本文能为蓝桥杯的准备提供有价值的参考。

转载地址：http://tkhfk.baihongyu.com/