1 条题解

  • 0
    @ 2025-7-3 18:18:26

    JAVA题解:

    import java.io.*;
    import java.util.*;
    
    public class Main {
        // 四个方向:上、下、左、右
        private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        public static void main(String[] args) throws IOException {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String[] dimensions = reader.readLine().trim().split(" ");
            int m = Integer.parseInt(dimensions[0]);
            int n = Integer.parseInt(dimensions[1]);
            
            char[][] grid = new char[m][n];
            for (int i = 0; i < m; i++) {
                String line = reader.readLine().trim();
                for (int j = 0; j < n; j++) {
                    grid[i][j] = line.charAt(j);
                }
            }
            
            System.out.println(shortestPath(grid));
        }
        
        /**
         * 计算从起点S到终点E的最短路径步数
         * 
         * @param grid 迷宫地图
         * @return 最短路径步数,如果无法到达则返回-1
         */
        public static int shortestPath(char[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            
            // 查找起点、终点和虫洞
            int startX = -1, startY = -1;
            List<int[]> wormholes = new ArrayList<>();
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 'S') {
                        startX = i;
                        startY = j;
                    } else if (grid[i][j] == '2') {
                        wormholes.add(new int[]{i, j});
                    }
                }
            }
            
            // 建立虫洞传送映射
            Map<String, int[]> teleport = new HashMap<>();
            for (int i = 0; i < wormholes.size(); i += 2) {
                if (i + 1 < wormholes.size()) {
                    int[] hole1 = wormholes.get(i);
                    int[] hole2 = wormholes.get(i + 1);
                    teleport.put(hole1[0] + "," + hole1[1], hole2);
                    teleport.put(hole2[0] + "," + hole2[1], hole1);
                }
            }
            
            // BFS查找最短路径
            Queue<int[]> queue = new LinkedList<>();
            boolean[][] visited = new boolean[m][n];
            
            // 将起点加入队列,格式:{x, y, 步数}
            queue.offer(new int[]{startX, startY, 0});
            visited[startX][startY] = true;
            
            while (!queue.isEmpty()) {
                int[] current = queue.poll();
                int x = current[0];
                int y = current[1];
                int steps = current[2];
                
                // 如果到达终点,返回步数
                if (grid[x][y] == 'E') {
                    return steps;
                }
                
                // 四个方向移动
                for (int[] dir : DIRECTIONS) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    
                    if (isValid(grid, nx, ny) && !visited[nx][ny] && grid[nx][ny] != '1') {
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny, steps + 1});
                    }
                }
                
                // 如果当前位置是虫洞,可以传送
                if (grid[x][y] == '2') {
                    String key = x + "," + y;
                    if (teleport.containsKey(key)) {
                        int[] dest = teleport.get(key);
                        int tx = dest[0];
                        int ty = dest[1];
                        
                        if (!visited[tx][ty]) {
                            visited[tx][ty] = true;
                            queue.offer(new int[]{tx, ty, steps}); // 传送不消耗步数
                        }
                    }
                }
            }
            
            // 无法到达终点
            return -1;
        }
        
        /**
         * 检查坐标是否在迷宫范围内且不是墙壁
         */
        private static boolean isValid(char[][] grid, int x, int y) {
            int m = grid.length;
            int n = grid[0].length;
            return x >= 0 && x < m && y >= 0 && y < n;
        }
    }
    
    
    • 1

    25年6月-华为实习(留学生)-2.迷宫最短路径

    信息

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