1 条题解

  • 0
    @ 2025-7-2 23:07:53

    JAVA题解:

    import java.util.*;
    import java.io.*;
    
    public class Main {
        // 使用静态内部类表示位置和步数
        static class Position {
            int row, col, steps;
            
            Position(int row, int col, int steps) {
                this.row = row;
                this.col = col;
                this.steps = steps;
            }
        }
        
        // 四个方向的移动
        private static final int[][] MOVES = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
        public static void main(String[] args) throws IOException {
            // 使用BufferedReader代替Scanner提高效率
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            
            // 读取攀爬能力
            int climbingPower = Integer.parseInt(reader.readLine().trim());
            
            // 读取地图尺寸
            String[] mapSize = reader.readLine().trim().split("\\s+");
            int height = Integer.parseInt(mapSize[0]);
            int width = Integer.parseInt(mapSize[1]);
            
            // 读取地图数据
            int[][] mountain = new int[height][width];
            for (int i = 0; i < height; i++) {
                String[] values = reader.readLine().trim().split("\\s+");
                for (int j = 0; j < width; j++) {
                    mountain[i][j] = Integer.parseInt(values[j]);
                }
            }
            
            // 计算并输出结果
            System.out.println(findShortestPath(mountain, climbingPower));
        }
        
        /**
         * 寻找从山底到山顶的最短路径
         */
        public static int findShortestPath(int[][] mountain, int climbingPower) {
            int height = mountain.length;
            int width = mountain[0].length;
            
            // 找到山底和山顶
            int startRow = -1, startCol = -1;
            int peakRow = -1, peakCol = -1;
            int maxHeight = -1;
            
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (mountain[i][j] == 0) {
                        startRow = i;
                        startCol = j;
                    }
                    
                    if (mountain[i][j] > maxHeight) {
                        maxHeight = mountain[i][j];
                        peakRow = i;
                        peakCol = j;
                    }
                }
            }
            
            // 使用BFS寻找最短路径
            boolean[][] explored = new boolean[height][width];
            Queue<Position> frontier = new LinkedList<>();
            
            // 加入起点
            frontier.offer(new Position(startRow, startCol, 0));
            explored[startRow][startCol] = true;
            
            while (!frontier.isEmpty()) {
                Position current = frontier.poll();
                
                // 到达山顶
                if (current.row == peakRow && current.col == peakCol) {
                    return current.steps;
                }
                
                // 尝试四个方向
                for (int[] move : MOVES) {
                    int nextRow = current.row + move[0];
                    int nextCol = current.col + move[1];
                    
                    // 检查边界和是否已探索
                    if (isValidPosition(nextRow, nextCol, height, width) && !explored[nextRow][nextCol]) {
                        // 检查高度差是否在攀爬能力范围内
                        int heightDifference = mountain[nextRow][nextCol] - mountain[current.row][current.col];
                        
                        if (Math.abs(heightDifference) <= climbingPower) {
                            explored[nextRow][nextCol] = true;
                            frontier.offer(new Position(nextRow, nextCol, current.steps + 1));
                        }
                    }
                }
            }
            
            // 无法到达山顶
            return -1;
        }
        
        /**
         * 检查位置是否在地图范围内
         */
        private static boolean isValidPosition(int row, int col, int height, int width) {
            return row >= 0 && row < height && col >= 0 && col < width;
        }
    }
    
    
    • 1

    信息

    ID
    17
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    4
    已通过
    1
    上传者