题目 广度优先搜索(一) - 抓住那头牛 广度优先搜索(一) - 迷宫 广度优先搜索(一) - 奇怪的电梯 广度优先搜索(一) - 仙岛求药 广度优先搜索(一) - 马的遍历 广度优先搜索(二) - 图像渲染 广度优先搜索(二) - 岛屿数量
广度优先搜索(一) - 抓住那头牛
题目分析
农夫和牛都位于数轴上，农夫希望通过最短的时间抓住牛。农夫可以选择三种不同的移动方式：向前一格、向后移动一格，或者是将当前位置乘以 2。每次移动花费一分钟，农夫的目标是抓住牛，并求出最少需要多少分钟。
这就是一个典型的图搜索问题，其中每个点代表数轴上的一个位置，每种移动方式都代表从当前点到相邻点的边。我们可以使用 广度优先搜索 (BFS) 来解决此问题，因为 BFS 可以保证找到最短路径。
关键点：
1. 题目可以视为在数轴上进行搜索，从农夫的起点 N 开始，尝试通过合法的移动方式走到牛的位置 K。
2. 由于 BFS 是无权图的最短路径算法，因此它非常适合解决此类问题。
输入输出
输入：
* 两个整数 N 和 K，分别表示农夫和牛的位置。
输出：
* 一个整数，表示农夫最少需要多少分钟才能抓住牛。
解题思路
1. 初始化状态：我们可以把每个位置视作一个节点，农夫从起点 N 开始，通过 BFS 找到最短时间到达牛的位置 K。
2. BFS搜索过程：
* 使用一个队列来进行广度优先搜索，队列保存当前节点的状态。
* 记录每个位置的最短时间，避免重复访问。
* 对每个当前位置进行三种可能的移动：
* 向左移动一格 (x-1)
* 向右移动一格 (x+1)
* 跳到 2*x
* 访问到牛的位置 K 时，直接输出当前的步数，即为所需的最少时间。
3. 边界条件：注意不要越界，即保证每个位置都在 [0, 100000] 范围内。
复杂度分析
* 时间复杂度：每个位置最多被访问一次，因此时间复杂度为 O(N)，其中 N = 100000。
* 空间复杂度：需要记录每个位置的最短步数，空间复杂度为 O(N)。
代码实现
广度优先搜索(一) - 迷宫
题目分析
给定一个迷宫，由若干行若干列的格子组成，部分格子被障碍物 # 占据，部分格子为空地 .。我们需要从迷宫的左上角（(1,1)）出发，走到右下角（(R, C)），求出最少的步数。每次移动只能在水平方向或垂直方向进行，不能斜着走，且起点和终点都是空地。
关键点：
* 最短路径问题：这是一个典型的图搜索问题，网格上的每个位置就是一个节点，能够走的格子是相邻的节点，目标是找出从起点到终点的最短路径。
* 使用广度优先搜索（BFS）：BFS 是解决无权图最短路径问题的经典算法，能够确保最先访问到的路径是最短路径。
输入输出
* 输入：
* 两个整数 R 和 C，表示迷宫的行数和列数。
* 接下来是 R 行，每行 C 个字符，表示迷宫布局。空地用 . 表示，障碍物用 # 表示。
* 输出：
* 输出从左上角 (1,1) 到右下角 (R, C) 的最小步数。
解题思路
1. 数据结构：
* 用一个 vis 数组记录每个位置是否被访问过。
* 使用一个队列 q 来进行广度优先搜索（BFS）。每次从队列中取出一个节点，处理它的四个邻居节点（上下左右），并加入队列。
2. BFS过程：
* 从起点 (1, 1) 开始，初始化步数为 0。
* 逐步遍历所有能走的路径，直到到达终点 (R, C)。
* 如果某个邻居节点是空地且未被访问过，加入队列，并记录其步数。
3. 结束条件：
* 当队列中出队的节点是终点 (R, C) 时，输出其步数。
4. 边界检查：
* 确保每次移动都不越界且目标位置是空地。
代码实现
广度优先搜索(一) - 奇怪的电梯
题目分析
在这道题目中，我们需要模拟一个奇怪的电梯。每个楼层都有一个数字，表示从当前楼层按“上”或“下”按钮时，电梯能到达的楼层。我们的目标是从楼层 A 到楼层 B，通过按按钮最少的次数来实现。
关键点：
* 电梯有四个按钮：开、关、上、下。每个楼层的数字 K[i] 指定了电梯能上下的层数（即当前楼层能到达的层数）。
* 我们需要用广度优先搜索（BFS）来找到从楼层 A 到楼层 B 的最短路径，因为这是一个最短路径问题，BFS 能有效地解决。
输入输出：
* 输入：
* N：楼层数
* A：起始楼层
* B：目标楼层
* K[i]：每个楼层上的数字，决定了电梯能上升或下降的楼层数。
* 输出：
* 输出从楼层 A 到楼层 B 所需的最少按键次数，若无法到达则输出 -1。
解题思路
1. 建模问题：
* 每个楼层可以看做一个节点，楼层之间的“上下”操作可以看做图中的边。
* BFS 能够保证找到从起点到终点的最短路径。
2. BFS过程：
* 从起始楼层 A 开始，初始化步数为 0。
* 每次按“上”按钮或“下”按钮移动，更新目标楼层。
* 遇到未访问的楼层，加入队列，并更新步数。
* 如果队列中取出的楼层是目标楼层 B，则输出步数并结束。
3. 边界条件：
* 如果楼层已访问过，就不再重复访问。
* 判断按“上”和“下”按钮是否能到达合法的楼层。
代码实现
广度优先搜索(一) - 仙岛求药
题目分析
这道题目是一个经典的路径最短问题，可以使用广度优先搜索（BFS）来求解。目标是在迷宫中寻找从起点（李逍遥的起始位置）到目标（仙药所在的位置）最短路径，同时避开含有怪物的方格。
关键点：
1. 迷阵描述：
* @：起始位置，李逍遥的起点。
* .：安全通行的方格。
* #：有怪物的方格，不能通行。
* *：仙药所在的位置，目标位置。
2. 移动规则：
* 可以在上下左右四个方向上移动。
* 只能经过 . 和 @ 方格，# 方格不能通行。
3. 要求：
* 使用最少的步数从起点 @ 移动到目标 *。
* 如果无法到达目标，输出 -1。
解题思路
1. 广度优先搜索（BFS）：
* BFS 是求解最短路径问题的经典算法，能够保证在无权图中找到从起点到目标的最短路径。
* BFS 通过逐层扩展来探索所有可能的路径，直到找到目标为止。
2. 步骤：
* 从起点 @ 开始进行 BFS。
* 每次访问一个新的方格时，记录它的步数。
* 使用队列来存储待访问的节点，每访问一个节点就检查其相邻的四个方向。
* 如果遇到目标 *，输出当前步数并结束。
* 如果队列空了还没有找到目标，说明无法到达目标，输出 -1。
3. 时间复杂度：
* BFS 的时间复杂度是 O(M * N)，其中 M 是迷阵的行数，N 是迷阵的列数。因为每个方格最多会被访问一次。
代码实现
广度优先搜索(一) - 马的遍历
题目分析
题目要求我们计算马从给定的起始位置到棋盘上每一个位置的最少步数，类似于一个多源最短路径问题，适合使用广度优先搜索（BFS）来求解。
关键点：
1. 马的移动方式：
* 马可以在棋盘上移动，每次可以选择8个方向：
* 每次移动的步数为 1。
2. 目标：
* 从给定的起点 (x, y) 开始，计算到达棋盘上每个位置的最少步数。
* 如果某个位置不可达，输出 -1。
3. 棋盘大小：
* 棋盘的大小为 n × m，最大为 400 × 400，即最多有 160,000 个格子。
4. 数据范围：
* 1 ≤ n, m ≤ 400
* 起始位置 (x, y) 是有效的位置，且 1 ≤ x ≤ n，1 ≤ y ≤ m。
解题思路
1. 广度优先搜索（BFS）：
* BFS 是解决单源最短路径问题的经典方法，适合处理这种图结构的最短步数问题。
* 使用 BFS 从起点 (x, y) 开始，逐步扩展到周围的格子，并更新到达每个格子的最短步数。
* 我们使用一个二维数组 dist 来存储每个格子的步数，初始化为 -1，表示不可达。起始点的步数为 0，然后通过 BFS 更新其他格子的步数。
2. 边界条件：
* 检查每次移动是否越界。
* 如果遇到不可达的格子，输出 -1。
3. 实现细节：
* 使用一个队列 queue 存储当前需要访问的格子。
* 从队列中取出一个格子，检查其相邻的8个格子，如果相邻格子在棋盘范围内且未被访问过，则将其加入队列并更新步数。
代码实现
广度优先搜索(二) - 图像渲染
题目分析
题目要求给定一个 n × m 的图像，并从一个指定的点 [x, y] 开始上色，将与该点相连且颜色相同的区域全部涂上一个新的颜色。
关键点：
1. 起始点与颜色：
* 从指定的点 [x, y] 开始上色，并将所有与该点相连（通过上下左右连接）的且颜色相同的区域，涂成目标颜色。
2. 问题性质：
* 这是一个图像区域上色问题，可以看作是一个 图的连通分量 问题。通过 BFS 或 DFS 遍历所有相连且颜色相同的点，逐一上色。
3. 数据范围：
* 图像的大小为 n × m，最大为 50 × 50，所以最大有 2500 个点，适合使用 BFS 或 DFS 来解决。
解题思路
1. BFS/DFS 进行区域遍历：
* 使用 BFS 或 DFS，从起始点 [x, y] 开始，遍历所有与之颜色相同的相连点，并将其涂上目标颜色。
* BFS 更适合处理这种遍历问题，使用队列来存储待访问的节点。
2. 边界检查：
* 在 BFS 中，要检查每次移动是否越界，同时确保当前点的颜色与起始点的颜色相同，才进行涂色操作。
3. 输出：
* 输出修改后的图像，每行打印一行。
代码实现
广度优先搜索(二) - 图像渲染
题目分析
我们需要将图像中的一部分进行上色，要求通过起始点 [x, y] 开始，递归地将与之相连且颜色相同的区域都改为目标颜色。此问题可以视为一个图像填充问题，类似于“油漆桶”问题。
关键点：
1. 上色的起始点：
* 从起始点 [x, y] 开始进行颜色更改。
2. 颜色传播：
* 需要遍历与起始点相连的所有区域（上下左右），并且颜色相同的区域都要改变成目标颜色。
3. 边界判断：
* 需要保证当前的操作不会越界，同时检查当前点的颜色是否与起始点颜色相同。
解题思路
1. BFS/DFS 进行区域填充：
* 使用 BFS 或 DFS 来从起始点开始逐步扩展区域，所有与起始点颜色相同的相邻区域都会被涂上目标颜色。
2. BFS 的好处：
* BFS 通过队列来逐步处理每一层的节点，适合处理这类层层扩展的区域问题。
3. 数据范围：
* 图像的大小为 n × m，最大为 50 × 50，所以最多有 2500 个点，适合使用 BFS 来解决。
代码实现
广度优先搜索(二) - 岛屿数量
题目分析
本题要求我们计算一个二维地图中岛屿的数量。地图由 1 和 0 组成，1 表示陆地，0 表示水域。岛屿是由连接在一起的陆地块组成的，陆地块通过水平方向或垂直方向相邻。如果两个陆地块通过一个连续的连接形成一个岛屿，则它们属于同一个岛屿。
思路
我们需要遍历整个地图，并对于每个陆地块（1），如果它没有被访问过，就启动一个 BFS 或 DFS 来标记与之相连的所有陆地块（将这些陆地块标记为 0 或已访问），然后统计岛屿的数量。
关键点：
* 岛屿定义：一个岛屿是由一群陆地块组成的，这些陆地块通过水平方向和垂直方向相邻连接。
* 遍历策略：使用广度优先搜索（BFS）或深度优先搜索（DFS）来遍历每个岛屿。每当遇到一个未被访问的陆地块（1），就启动 BFS/DFS 来遍历并标记所有与之连接的陆地块。
* 边界检查：在进行搜索时，需要确保不会访问到地图外部的区域。
BFS/DFS
* BFS：广度优先搜索通过队列来处理每个陆地块，并逐步检查它的相邻块。
* DFS：深度优先搜索通过递归来处理每个陆地块，并访问所有相连的陆地块。
解题思路：
1. 对每个陆地块进行遍历。
2. 如果当前陆地块没有被访问过，就启动 BFS/DFS 来标记所有与它相连的陆地块，并增加岛屿数量。
3. 最终输出岛屿的总数。
代码实现
