华为OD机试 - 西天取经 - 广度优先搜索BFS（Java 2024 E卷 200分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
唐僧师徒四人去西天取经，一路翻山越岭。一天，师徒四人途径一个 m×n 长方形区域，已知：
- 将取经队伍作为一个整体，4人行走相同路线。
- 取经队伍的起点为该长方形区域的左上角，目的地为该长方形区域的右下角。
- 行走路线可以向前、后、左、右四个方向前进（不允许直线上下向对角线移动）。
- 输入包含该区域的 m 行 n 列的整数 h，前后移动允许的高度差为 t 表示。
- 要求该区域内的取经队伍移动的高度差在高度 t 的限制内，取经队伍最多有 3 次爆发机会，每使用一次爆发机会，可以让取经队伍任意一次移动突破高度差限制。
请编写程序，队伍通过该区域的移动次数是多少次回合，表示师徒四人无法直接通过该区域。
二、输入描述
输入第一行有三个整数，分别对应为长方形场地的两条边长，和前后移动允许的高度差。三个整数之间以空格分割。后面是 m 行，n 列的整数矩阵 h，表示长方形场地各点的高度。数据量 m ≤ 200，n ≤ 200，t ≤ 20。
每个 h 的高度 h 满足 20 ≤ h ≤ 4000，0 ≤ i ≤ m，0 ≤ j ≤ n。
三、输出描述
一个 整数 表示队伍通过该区域最少的移动次数。
四、测试用例
测试用例1：
1、输入
4 4 10
10 20 30 40
100 120 140 160
200 230 260 290
300 400 500 600
2、输出
6
3、说明
树苗分别种植在位置 (0,0)=10、(0,3)=40、(1,3)=160、(2,3)=290、(3,3)=600，使用了3次爆发机会，移动次数为6次。
测试用例2：
1、输入
1 10 1
11 12 200 14 15 16 317 18 19 20
2、输出
-1
3、说明
在一行10个坑位的位置中，爆发机会最多使用3次，但无法从起点 (0,0)=11 移动到终点 (0,9)=20，因为需要使用4次爆发机会，超过了限制。因此，输出 -1。
测试用例3：
1、输入
2 2 3
1 4
5 8
2、输出
2
3、说明
起点 (0,0)=1。
移动路径：
(0,0)=1 -> (1,0)=5：diff=4 >3，使用爆发1。
(1,0)=5 -> (1,1)=8：diff=3 ≤3，不用爆发。
总移动次数：2。
使用了1次爆发机会。
五、解题思路
1、广度优先搜索BFS
本题涉及在一个二维网格中从起点移动到终点，同时需要考虑移动过程中的高度差限制和爆发机会。
- 广度优先搜索（BFS）：由于要求找到最少的移动次数，BFS 是一个合适的选择，因为它天然适用于寻找最短路径的问题。
- 状态表示：每个状态由 (i, j, k) 组成，其中 (i, j) 表示当前位置，k 表示已使用的爆发机会次数（0 <= k <= 3）。
- 访问标记：为了避免重复访问同一状态，使用一个三维布尔数组 visited[m][n][4] 来标记是否已经访问过 (i, j, k) 状态。
- 移动逻辑：
- 从当前格子向四个方向移动。
- 计算高度差，根据高度差决定是否需要使用爆发机会。
- 如果需要使用爆发机会且 k < 3，则可以移动并将 k 加一。
- 将新的状态加入队列中进行下一轮的搜索。
2、关键点
- 爆发机会的管理：爆发机会是有限的资源，需要在必要时使用。
- 状态管理：不仅要记录位置，还要记录已使用的爆发机会次数，以确保不同的使用方式不会互相影响。
- 边界条件：
- 起点即为终点时，移动次数为 0。
- 需要种植的树苗数量大于坑位数量时，输出 -1。
- 处理单行或单列的网格。
3、数据结构的选择
队列（Queue）：用于实现 BFS，保证按照层级顺序进行搜索。
三维布尔数组：高效地记录和查询是否访问过特定的状态，避免重复计算。
二维数组：存储网格的高度值，便于快速访问和计算。
六、Java算法源码
public class OdTest01 {
/**
* 状态类，表示当前的位置和已使用的爆发机会次数。
*/
static class State {
int x; // 当前行坐标
int y; // 当前列坐标
int used; // 已使用的爆发机会次数
public State(int x, int y, int used) {
this.x = x;
this.y = y;
this.used = used;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取第一行，包含m, n, t
String[] firstLine = scanner.nextLine().trim().split("\\s+");
int m = Integer.parseInt(firstLine[0]); // 行数
int n = Integer.parseInt(firstLine[1]); // 列数
int t = Integer.parseInt(firstLine[2]); // 允许的高度差
// 初始化高度矩阵
int[][] h = new int[m][n];
// 读取m行，每行n个高度值
for(int i = 0; i < m; i++) {
String[] line = scanner.nextLine().trim().split("\\s+");
for(int j = 0; j < n; j++) {
h[i][j] = Integer.parseInt(line[j]);
}
}
scanner.close(); // 关闭扫描器
// 定义最大爆发机会次数
final int MAX_USED = 3;
// 初始化访问标记数组，维度为[m][n][4]
boolean[][][] visited = new boolean[m][n][MAX_USED + 1];
// 初始化队列并加入起点状态
Queue<State> queue = new LinkedList<>();
queue.offer(new State(0, 0, 0));
visited[0][0][0] = true;
// 如果起点即为终点，移动次数为0
if(m == 1 && n == 1) {
System.out.println(0);
return;
}
// 定义移动方向：上、下、左、右
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int steps = 0; // 移动次数
// 开始BFS搜索
while(!queue.isEmpty()) {
int size = queue.size(); // 当前层的状态数量
steps++; // 每层代表一次移动
// 逐个处理当前层的所有状态
for(int i = 0; i < size; i++) {
State current = queue.poll();
// 遍历四个可能的移动方向
for(int dir = 0; dir < 4; dir++) {
int newX = current.x + dx[dir];
int newY = current.y + dy[dir];
int newUsed = current.used; // 新状态的爆发机会次数
// 检查新位置是否在网格范围内
if(newX < 0 || newX >= m || newY < 0 || newY >= n) {
continue; // 越界，跳过
}
// 计算高度差
int heightDiff = Math.abs(h[newX][newY] - h[current.x][current.y]);
// 判断是否需要使用爆发机会
if(heightDiff > t) {
newUsed += 1; // 需要使用一次爆发机会
if(newUsed > MAX_USED) {
continue; // 爆发机会已用完，无法移动
}
}
// 如果新状态未被访问过，则加入队列
if(!visited[newX][newY][newUsed]) {
visited[newX][newY][newUsed] = true; // 标记为已访问
queue.offer(new State(newX, newY, newUsed));
// 如果到达终点，返回当前的移动次数
if(newX == m-1 && newY == n-1) {
System.out.println(steps);
return;
}
}
}
}
}
// 如果无法到达终点，输出-1
System.out.println(-1);
}
}
七、效果展示
1、输入
3 3 5
1 6 11
6 12 18
11 18 25
2、输出
4
3、说明
起点 (0,0)=1。
移动路径：
(0,0)=1 -> (0,1)=6：diff=5 ≤5，不用爆发。
(0,1)=6 -> (1,1)=12：diff=6 >5，使用爆发1。
(1,1)=12 -> (2,1)=18：diff=6 >5，使用爆发2。
(2,1)=18 -> (2,2)=25：diff=7 >5，使用爆发3。
总移动次数：4。
使用了3次爆发机会，符合限制。
🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）
🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
