题解 | #走迷宫#
走迷宫
https://www.nowcoder.com/practice/e88b41dc6e764b2893bc4221777ffe64
//package 搜索.BFS.走迷宫; import java.io.*; import java.util.*; class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); String[] nums = in.readLine().split(" "); int n = Integer.parseInt(nums[0]); int m = Integer.parseInt(nums[1]); nums = in.readLine().split(" "); int xb = Integer.parseInt(nums[0]) - 1; // 调整索引,以0开始 int yb = Integer.parseInt(nums[1]) - 1; int xe = Integer.parseInt(nums[2]) - 1; int ye = Integer.parseInt(nums[3]) - 1; // 初始化迷宫和访问状态 char[][] graph = new char[n][m]; boolean[][] visited = new boolean[n][m]; int[][] dist = new int[n][m]; for (int i = 0; i < n; i++) { graph[i] = in.readLine().toCharArray(); Arrays.fill(dist[i], Integer.MAX_VALUE); } in.close(); // BFS Queue<Point> queue = new LinkedList<>(); queue.add(new Point(xb, yb)); dist[xb][yb] = 0; int[] dx = {-1, 1, 0, 0}; // 方向数组 int[] dy = {0, 0, -1, 1}; while (!queue.isEmpty()) { Point current = queue.poll(); if (current.x == xe && current.y == ye) { out.write(dist[xe][ye] + ""); out.close(); return; } //依次访问上下左右点 for (int i = 0; i < 4; i++) { int nx = current.x + dx[i]; int ny = current.y + dy[i]; // 检查新坐标是否有效 if (nx >= 0 && nx < n && ny >= 0 && ny < m && graph[nx][ny] == '.' && !visited[nx][ny]) { visited[nx][ny] = true; dist[nx][ny] = dist[current.x][current.y] + 1; queue.add(new Point(nx, ny)); } } } out.write("-1"); // 如果没有路径 out.close(); } }