第三题
题目
给定一个二维数组 mountainMap 表示一座山的地图，数组中的每个元素 mountainMap[x][y] 代表坐标 (x, y) 处山的高度。登山员从山底出发，爬到山峰。
山底的含义：mountainMap中高度为0的坐标点。
山峰的含义：mountainMap中高度最高的坐标点。
登山员每次移动只能从当前位置向上下左右四个方向移动一格，向高处移动时，移动到的位置山的高度不能高于当前位置的高度加上固定的攀登能力值climbAbility；向低处移动时，移动到的位置的山的高度不能低于当前位置山的高度减去climbAbility。
变量取值范围：
climbAbility:[1,30]
山峰高度:[0,100]
mountainMap的行数mountainMapRows:[2,1000]
mountainMap的列数mountainMapCols:[2,1000]
请计算出从山底移动到山峰，最少需要移动几次？
解答要求：时间限制: C/C++ 1000ms，其他语言: 2000ms 内存限制: C/C++ 256MB，其他语言: 512MB
输入格式
第一行为climbAbility的值
第二行为mountainMapRows mountainMapCols
从第三行开始为mountainMapRows行mountainMapCols列的高度二维数组mountainMap[mountainMapRows][mountainMapCols]，每行的高度数字中间用空格分割
输出格式
从山底移动到山峰，最少移动次数。 如果无法移动至山峰，则输出-1
示例1
输入
2
3 2
1 3
0 4
5 3
输出5
解释
攀登能力为2，3行2列的山峰坐标，山底的坐标为(1,0)高度0，山峰的坐标为(2,0)高度5。仅有一条路线 初始位置山底(1,0)高度0->(0,0)高度1->(0,1)高度3->(1,1)高度4->(2,1)高度3->(2,0)高度5 共需要移动5次
示例2
输入1
4 5
1 1 1 1 1
1 0 1 2 1
1 1 1 3 1
1 1 1 1 1
输出3
解释
攀登能力为1，4行5列的山峰坐标，山底的坐标为(1,1)，山峰的坐标为(2,3)。 最短路线为 初始位置山底(1,1)高度0->(1,2)高度1->(1,3)高度2->山峰(2,3)高度3 共需要移动3次
示例3
输入1
4 5
1 1 1 1 1
1 0 1 2 1
1 1 1 0 1
1 1 1 1 1
输出-1
解释
无法达到山峰，输出-1
代码
package main.huawei;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @ClassName MountainGraph
* @Description 华为0528笔试题
* @Author Feng
* @Date 2025/6/9
**/
public class MountainGraph {
private static int[][] DIRECTIONS = {{-1,0},{1,0},{0,-1},{0,1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int climbAblity = sc.nextInt();
int rows = sc.nextInt();
int cols = sc.nextInt();
sc.nextLine();
int[][] mountain = new int[rows][cols];
int[] bottom = null;
int[] peak = null;
int maxHeight = -1;
for (int i = 0; i < rows; i++) {
String[] line = sc.nextLine().split(" ");
for (int j = 0; j < cols; j++) {
mountain[i][j] = Integer.parseInt(line[j]);
// 找到谷底
if (mountain[i][j] == 0) {
bottom = new int[]{i, j};
}
// 找到山顶
if (mountain[i][j] > maxHeight) {
maxHeight = mountain[i][j];
peak = new int[]{i, j};
}
}
}
// 计算从谷底到山顶的最短路径
int min = minPath(climbAblity, mountain, bottom, peak, maxHeight);
System.out.println("min = " + min);
}
/**
* 计算从山谷到山顶的最短路径
**/
private static int minPath(int climbAblity, int[][] mountain, int[] bottom, int[] peak, int maxHeight) {
// 用于标识每个节点是否已经访问过
boolean[][] visited = new boolean[mountain.length][mountain[0].length];
Queue<int[]> queue = new LinkedList<>();
// 将起始节点加入队列, 并标记为已访问
queue.offer(new int[]{bottom[0], bottom[1], 0}); // {row, col, steps}
visited[bottom[0]][bottom[1]] = true;
while (!queue.isEmpty()) {
// 取出队首节点
int[] current = queue.poll();
int row = current[0];
int col = current[1];
int steps = current[2];
// 如果当前节点为山顶，返回步数
if (row == peak[0] && col == peak[1]) {
return steps;
}
// 遍历四个方向
for (int[] dir : DIRECTIONS) {
int newRow = row + dir[0];
int newCol = col + dir[1];
// 检查新位置是否越界
if (newRow >= 0 && newRow < mountain.length && newCol >= 0 && newCol < mountain[0].length){
int nextHeight = mountain[newRow][newCol];
if (!visited[newRow][newCol] && nextHeight <= climbAblity+mountain[row][col] &&
nextHeight >= mountain[newRow][newCol]-climbAblity) {
visited[newRow][newCol] = true;
queue.offer(new int[]{newRow, newCol, steps + 1});
}
}
}
}
// 若不存在最短路径，则返回-1
return -1;
}
}
最少步数问题，使用bfs算法来寻找从山底到山峰的最短路径。 主要思路是： 读取输入数据并找到山底和山峰的坐标 初始化 BFS 队列，从山底开始搜索 每次从队列中取出当前位置，检查四个方向的可能移动 若移动符合高度差限制且未访问过，则加入队列继续搜索 找到山峰时立即返回步数，若队列为空仍未找到则返回 - 1 时间复杂度：O (m*n)