1 条题解
-
0
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
- 上传者