华为OD 周末爬山
题目描述：
周末小明准备去爬山锻炼，0代表平地，山的高度使用1到9来表示，小明每次爬山或下山高度只能相差k及k以内，每次只能上下左右一个方向上移动一格，小明从左上角(0,0)位置出发
输入描述：
第一行输入m n k(空格分隔)
·代表m*n的二维山地图，k为小明每次爬山或下山高度差的最大值，然后接下来输入山地图，一共m行n列，均以空格分隔。取值范围：
·0<m≤500
·O<n≤500
·0<k<5
输出描述
请问小明能爬到的最高峰多高，到该最高峰的最短步数，输出以空格分隔。同高度的山峰输出较短步数。
如果没有可以爬的山峰，则高度和步数都返回0。
备注
所有用例输入均为正确格式，且在取值范围内，考生不需要考虑不合法的输入格式。
输入
5 4 1
0 1 2 0
1 0 0 0
1 0 1 2
1 3 1 0
0 0 0 9
输出
22
说明
根据山地图可知，能爬到的最高峰在(0,2)位置，高度为2,最短路径为(0,0)-(0,1)-(0.2),最短步数为2。用例2
5 4 3
0 0 0 0
0 0 0 0
0 9 0 0
0 0 0 0
0 0 0 9
0 0
根据山地图可知，每次爬山距离3,无法爬到山峰上，步数为0。
package bfs;import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;public class MountainClimbing {public static int k;//key = 山峰高度 value = 步数public static Map<Integer, Integer> map = new HashMap<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);//读取第一行输入 m n kString[] line1 = sc.nextLine().split(" ");int m = Integer.parseInt(line1[0]);int n = Integer.parseInt(line1[1]);k = Integer.parseInt(line1[2]);//读取二维数组int[][] matrix = new int[m][n];for (int i = 0; i <= m - 1; i++) {String[] line = sc.nextLine().split(" ");for (int j = 0; j <= n - 1; j++) {matrix[i][j] = Integer.parseInt(line[j]);}}bfs(matrix, 0, 0);
// dfs(matrix, 0, 0, 0);int maxValue = 0;int step = 0;for(int value : map.keySet()) {if (value > maxValue) {maxValue = value;step = map.get(value);}}System.out.println(maxValue + " " + step);}public static void bfs(int[][] matrix, int row, int col) {Queue<int[]> queue = new LinkedList<>();// 行、列、层级（步数）queue.offer(new int[]{row, col, 0});// 记录四个方向的偏移量int[][] offsets = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};while (!queue.isEmpty()) {int[] current = queue.poll();int x = current[0];int y = current[1];//表示当前节点已被访问过if (matrix[x][y] < 0) {continue;}// 如果map中不包含此高峰高度，或者当前节点步数少。if(!map.containsKey(matrix[x][y]) || map.get(matrix[x][y]) > current[2]) {map.put(matrix[x][y], current[2]);}int val = matrix[x][y];matrix[x][y] = -1;//四个方向遍历for(int[] offset : offsets) {int newX = x + offset[0];int newY = y + offset[1];// 节点越界// 节点访问过// 山峰高度相差大于K 无法到达此节点if (newX < 0 || newX >= matrix.length || newY < 0 || newY >= matrix[0].length ||matrix[newX][newY] < 0 || Math.abs(matrix[newX][newY]) - val > k) {continue;}queue.offer(new int[]{newX, newY, current[2] + 1});}}}public static void dfs(int[][] matrix, int row, int col, int step) {int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int val = matrix[row][col];//如果当前山峰高度再map中没有，直接put高度以及步数//如果当前山峰走的步数小于之前走的步数，替换之前的步数if (!map.containsKey(val) || step < map.get(val)) {map.put(val, step);}//标记当前节点已经走过，不走回头路matrix[row][col] = -1;// 四个方向遍历for(int[] offset : offsets) {int newRow = row + offset[0];int newCol = col + offset[1];if (newRow < 0 || newRow >= matrix.length || newCol < 0 || newCol >= matrix[0].length || matrix[newRow][newCol] < 0) {continue;}if (Math.abs(val - matrix[newRow][newCol]) <= k) {dfs(matrix, newRow, newCol, step + 1);}}//恢复当前节点的值，matrix[row][col] = val;}}