题目 【广度优先搜索(三)】二进制矩阵中的最短路径 【广度优先搜索(三)】观星 【广度优先搜索(三)】求细胞数量 【广度优先搜索(三)】打开转盘锁
【广度优先搜索(三)】二进制矩阵中的最短路径
题目描述
给定一个 n x n 的二进制矩阵，其中每个元素为 0 或 1。我们从矩阵的左上角 (0, 0) 出发，尝试找到一条路径到达右下角 (n-1, n-1)。该路径必须满足：
* 路径经过的所有单元格的值是 0。
* 路径中相邻的单元格必须是上下左右或对角线方向相连。
* 如果路径存在，返回最短路径的长度；如果没有路径，返回 -1。
输入格式
* 第一行输入一个整数 n，表示矩阵的维度 n x n。
* 接下来输入 n 行，每行包含 n 个数字，其中每个数字是 0 或 1，表示该位置是否可以走通。
输出格式
* 输出一个整数，表示从左上角到右下角的最短路径长度。如果没有路径，输出 -1。
解题思路
这是一个典型的最短路径问题，可以使用 广度优先搜索 (BFS) 来解决，因为 BFS 可以找到无权图中从起点到终点的最短路径。
关键步骤：
1. BFS遍历：使用队列从 (0, 0) 开始遍历，沿着可能的路径逐步扩展，记录每个位置的最短距离。
2. 边界条件：如果遇到障碍物（1）或者超出了矩阵范围，则跳过该位置。
3. 八个方向：由于可以在上下左右及四个对角线方向上移动，使用八个方向数组来控制遍历。
4. 终止条件：一旦到达右下角 (n-1, n-1)，即返回该位置的最短路径长度。如果 BFS 结束后仍未到达，返回 -1。
代码实现
【广度优先搜索(三)】观星
题目描述
给定一个长方形的星空网格，网格中有星星（用 * 表示）和空白区域（用 . 表示）。相邻的星星（包括对角线方向上的相邻）视为同一个星座。我们需要计算星空中有多少个星座，并且输出最大星座的大小（即最大星系包含的星星数量）。
解题思路
这个问题可以通过广度优先搜索（BFS）或者深度优先搜索（DFS）来解决，目的是找到所有相邻的星星并将它们标记为同一个星座。
* BFS/DFS遍历：从每个未访问的星星开始，遍历与它相连的星星，并标记它们为已访问。每次遍历一个新的星星时，都会形成一个新的星座。
* 方向数组：我们可以使用一个方向数组来帮助我们实现8个方向的移动，包括上下左右和4个对角线方向。
* 统计星座大小：每次找到一个新的星座时，记录下该星座的大小，并统计星座的数量。
* 最大星座：更新并记录最大星座的大小。
步骤
1. 输入矩阵：首先读取一个 N x M 的矩阵，表示星空。
2. BFS/DFS：从每个未访问的星星开始，使用 BFS 或 DFS 遍历与它相连的所有星星，计算该星座的大小。
3. 统计：统计所有星座的大小，并更新最大星座的大小。
4. 输出结果：输出星座的数量和最大星座的大小。
代码实现
【广度优先搜索(三)】求细胞数量
题目描述
在一个由数字 0 到 9 构成的矩阵中，数字 1 到 9 代表不同的细胞。细胞是通过上下左右方向连接的数字相邻区域的组合，要求求出矩阵中细胞的个数。
解题思路
这个问题可以通过广度优先搜索（BFS）或者深度优先搜索（DFS）来解决。每个细胞都是由相邻的数字 1-9 组成的区域，我们需要找到这些区域，并统计区域的个数。由于每个细胞的数字值都可能是 1-9，我们需要分别处理每个区域，判断其是否属于同一细胞。
步骤
1. 读取输入：首先读取矩阵的大小和矩阵本身。
2. 构建地图：用二维数组 Map 来存储矩阵信息。每个位置的值是 true（表示细胞）或者 false（表示空白）。
3. 遍历矩阵：使用 BFS 或 DFS 来遍历每个未访问过的细胞，统计每个细胞区域的个数。
4. BFS/DFS 实现：对于每个未访问的细胞，启动 BFS 或 DFS，从该细胞开始遍历所有与其相邻的细胞，并将它们标记为已访问，防止重复计数。
5. 输出结果：最终输出细胞的数量。
代码实现
【广度优先搜索(三)】打开转盘锁
题目描述
给定一个四位数字密码锁，密码的每一位都可以进行两种操作：
1. 将某一位数字增加 1，如果对 9 操作将会变为 1。
2. 将某一位数字减少 1，如果对 1 操作将会变为 9。
我们需要从当前密码到目标密码，求最少的操作次数。
解题思路
本题是典型的 广度优先搜索 (BFS) 应用，BFS 可以有效地求解从起始状态到目标状态的最短路径问题。在这个问题中，每个状态表示一个四位数的密码，每次可以进行两种操作，BFS 通过遍历所有可能的状态，并且寻找从起始状态到目标状态的最短路径。
具体步骤
1. 状态表示：将密码的每一位数字表示为一个状态，因此密码是一个包含四个数字的状态 (num[0], num[1], num[2], num[3])。
2. 状态转移：每次操作可以选择加一或减一某一位数字，产生一个新的状态。
3. 广度优先搜索：从初始状态开始，使用队列保存状态，逐步扩展所有可以到达的状态。当目标状态被找到时，返回当前步数。
BFS 过程
1. 初始化：将起始密码状态入队，初始化步数为 0。
2. 队列操作：对于队列中的每个状态，尝试通过加一或减一某一位数字来生成新的状态。
3. 终止条件：如果当前状态为目标密码，返回当前的步数。
4. 已访问标记：使用 vis 数组记录已经访问过的状态，避免重复处理。
代码实现
