网站建设专家如何选,谷歌搜索引擎下载,校园网站建设结论,国内做贵金属返佣比较多的网站1、题目描述
【西天取经】 唐僧师徒四人去西天取经#xff0c;一路翻山越岭。一日#xff0c;师徒四人途径一个 mxn 长方形区域#xff0c;已知 1.将取经队伍作为一个整体#xff0c;4 人行走相同路线。 2.取经队伍的起点为该长方形区域的左上角#xff0c;目的地为该长方…1、题目描述
【西天取经】 唐僧师徒四人去西天取经一路翻山越岭。一日师徒四人途径一个 mxn 长方形区域已知 1.将取经队伍作为一个整体4 人行走相同路线。 2.取经队伍的起点为该长方形区域的左上角目的地为该长方形区域的右下角 3.行走路线可以向前、后、左、右四个方向前进 (不允许超出该长方形区域) 4.输入包含该区域的长 m 和宽 n、前后移动允许的高度差 t以及该长方形区域内各点的高度 h。 5.要求该区域内相邻两次移动的高度差在高度 t 范围以内。取经队伍最多有 3 次爆发机会每使用一次爆发机会可以让取经队伍一次移动突破高度差限制 请问取经队伍通过该区域最小的移动次数是多少返回 -1 表示师徒四人无法直接通过该区域。
【输入描述】 输入第一行为三个整数分别对应为长方形场地的两条边长和前后移动允许的高度差。三个整数之间以空格分割。 后面是m行每行n列个数据表示长方形场地各点的高度。数据之间以空格分割。 0mn2000t20 每个点的高度hin满足0h[i,j]40000im 0jn。
【输出描述】 取经队伍通过该区域最小的移动次数
【示例一】 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上班之路
