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

素颜马尾好姑娘i 2023-10-10 17:54 25阅读 0赞

#### 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）[士兵突击][Link 1]  
（2）[上班之路][Link 2]

[Link 1]: https://blog.csdn.net/weixin_43763430/article/details/130716778
[Link 2]: https://blog.csdn.net/weixin_43763430/article/details/130695583