第三題
題目
給定一個二維數組 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});}}}}// 若不存在最短路徑，則返回-1return -1;}
}最少步數問題，使用bfs算法來尋找從山底到山峰的最短路徑。 主要思路是： 讀取輸入數據并找到山底和山峰的坐標 初始化 BFS 隊列，從山底開始搜索 每次從隊列中取出當前位置，檢查四個方向的可能移動 若移動符合高度差限制且未訪問過，則加入隊列繼續搜索 找到山峰時立即返回步數，若隊列為空仍未找到則返回 - 1 時間復雜度：O (m*n)
”)
