题解 | 走迷宫

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
import java.util.*;

public class Main {
    static int n, m;
    static int xs, ys, xe, ye;
    static char[][] graph = new char[1010][1010];
    static int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取迷宫尺寸和坐标
        n = in.nextInt();
        m = in.nextInt();
        xs = in.nextInt();
        ys = in.nextInt();
        xe = in.nextInt();
        ye = in.nextInt();
        in.nextLine(); // 消耗掉剩余的换行符，避免影响后续读取
        
        // 读取迷宫内容（使用hasNextLine判断）
        for (int i = 0; i < n; i++) {
            String line = in.nextLine();
            graph[i] = line.toCharArray();
        }
        
        // 调用BFS（注意坐标转换为0-based）
        System.out.println(bfs(graph, xs - 1, ys - 1, xe - 1, ye - 1));
    }

    public static int bfs(char[][] graph, int xs, int ys, int xe, int ye) {
        // 检查输入合法性
        if (graph == null || graph.length == 0 || graph[0].length == 0) {
            return -1;
        }
        // 检查起点和终点是否为障碍物
        if (graph[xs][ys] == '*' || graph[xe][ye] == '*') {
            return -1;
        }
        
        boolean[][] vis = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{xs, ys, 0});
        vis[xs][ys] = true;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int steps = current[2];
            
            // 到达终点，返回步数
            if (x == xe && y == ye) {
                return steps;
            }
            
            // 探索四个方向
            for (int[] dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                // 检查新位置是否合法：在范围内、非障碍物、未访问
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (graph[nx][ny] != '*' && !vis[nx][ny]) {
                        vis[nx][ny] = true; // 确认合法后再标记访问
                        queue.add(new int[]{nx, ny, steps + 1});
                    }
                }
            }
        }
        // 无法到达终点
        return -1;
    }
}