1 条题解
-
0
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
信息
- ID
- 19
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者