华为OD机试真题【西天取经】

1、题目描述

【西天取经】
唐僧师徒四人去西天取经，一路翻山越岭。一日，师徒四人途径一个 mxn 长方形区域，已知
1.将取经队伍作为一个整体，4 人行走相同路线。
2.取经队伍的起点为该长方形区域的左上角，目的地为该长方形区域的右下角
3.行走路线可以向前、后、左、右四个方向前进 (不允许超出该长方形区域)
4.输入包含该区域的长 m 和宽 n、前后移动允许的高度差 t，以及该长方形区域内各点的高度 h。
5.要求该区域内相邻两次移动的高度差在高度 t 范围以内。取经队伍最多有 3 次爆发机会，每使用一次爆发机会，可以让取经队伍一次移动突破高度差限制
请问取经队伍通过该区域最小的移动次数是多少？返回 -1 表示师徒四人无法直接通过该区域。

【输入描述】
输入第一行为三个整数，分别对应为长方形场地的两条边长，和前后移动允许的高度差。三个整数之间以空格分割。
后面是m行，每行n列个数据，表示长方形场地各点的高度。数据之间以空格分割。
0<m，n<=200，0<t<=20
每个点的高度hin满足0<=h[i,j]<=4000，0<=i<m 0<=j<n。

【输出描述】
取经队伍通过该区域最小的移动次数

【示例一】
4 4 10
10 20 30 40
100 120 140 160
200 230 260 290
300 400 500 600
输出
6

【示例二】
输入
1 10 1
11 12 200 14 15 16 317 18 19 20
输出
-1

2、解题思路

该题是从左上角到右下角，与上班之路一样的思路，从左上角开始向上、下、左、右遍历，取到达右下角的最小移动步数。

3、参考代码

import java.util.Scanner;/*** @Author * @Date 2023/5/7 12:20*/
public class 西天取经 {public static int[][] dis = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};public static int res = Integer.MAX_VALUE;public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {int m = in.nextInt();int n = in.nextInt();int k = in.nextInt();int[][] arr = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {arr[i][j] = in.nextInt();}}res = Integer.MAX_VALUE;for (int i = 0; i < dis.length; i++) {boolean[][] used = new boolean[m][n];used[0][0] = true;dfs(arr, dis[i][0], dis[i][1], k, 1, used, 3);}if (res == Integer.MAX_VALUE) {System.out.println(-1);} else {System.out.println(res);}}}public static void dfs(int[][] arr, int i, int j, int k, int sum, boolean[][] used, int bf) {int m = arr.length;int n = arr[0].length;if (i < 0 || i >= m || j < 0 || j >= n) {return;}// 到达右下角if (i == m - 1 && j == n - 1) {// 取移动步数最小的结果res = Math.min(res, sum);return;}used[i][j] = true;// 分别遍历四个方向for (int l = 0; l < dis.length; l++) {int newI = i + dis[l][0];int newJ = j + dis[l][1];if (newI < 0 || newI>= m || newJ < 0 || newJ >= n) {continue;}if (used[newI][newJ]) {continue;}if (Math.abs(arr[i][j] - arr[newI][newJ]) <= k) {dfs(arr, newI, newJ, k, sum + 1, used, bf);} else {if (bf == 0) {  // 爆发次数用完了continue;}dfs(arr, newI, newJ, k, sum + 1, used, bf - 1);}}used[i][j] = false;}
}

4、相似题目

（1）士兵突击
（2）上班之路