华为OD机试 - 西天取经 - 广度优先搜索BFS（Java 2024 E卷 200分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

唐僧师徒四人去西天取经，一路翻山越岭。一天，师徒四人途径一个 m×n 长方形区域，已知：

1. 将取经队伍作为一个整体，4人行走相同路线。
2. 取经队伍的起点为该长方形区域的左上角，目的地为该长方形区域的右下角。
3. 行走路线可以向前、后、左、右四个方向前进（不允许直线上下向对角线移动）。
4. 输入包含该区域的 m 行 n 列的整数 h，前后移动允许的高度差为 t 表示。
5. 要求该区域内的取经队伍移动的高度差在高度 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

本题涉及在一个二维网格中从起点移动到终点，同时需要考虑移动过程中的高度差限制和爆发机会。

1. 广度优先搜索（BFS）：由于要求找到最少的移动次数，BFS 是一个合适的选择，因为它天然适用于寻找最短路径的问题。
2. 状态表示：每个状态由 (i, j, k) 组成，其中 (i, j) 表示当前位置，k 表示已使用的爆发机会次数（0 <= k <= 3）。
3. 访问标记：为了避免重复访问同一状态，使用一个三维布尔数组 visited[m][n][4] 来标记是否已经访问过 (i, j, k) 状态。
4. 移动逻辑：
   • 从当前格子向四个方向移动。
   • 计算高度差，根据高度差决定是否需要使用爆发机会。
   • 如果需要使用爆发机会且 k < 3，则可以移动并将 k 加一。
   • 将新的状态加入队列中进行下一轮的搜索。

2、关键点

1. 爆发机会的管理：爆发机会是有限的资源，需要在必要时使用。
2. 状态管理：不仅要记录位置，还要记录已使用的爆发机会次数，以确保不同的使用方式不会互相影响。
3. 边界条件：
   • 起点即为终点时，移动次数为 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, tString[] 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;// 如果起点即为终点，移动次数为0if(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;}}}}}// 如果无法到达终点，输出-1System.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在线答疑。