题解 | 走迷宫

import java.io.*;
import java.util.*;

public class Main {
    /**
    * 主方法，处理输入输出并调用BFS算法
    *
    * @param args 命令行参数
    * @throws IOException 可能抛出IO异常
    */
    public static void main(String[] args) throws IOException {
// 使用BufferedReader读取输入，使用PrintWriter输出
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

// 读取第一行输入，分割成字符串数组并解析为整数n和m
        String[] strA = br.readLine().trim().split("\\s+");
        int n = Integer.parseInt(strA[0]); // 行数
        int m = Integer.parseInt(strA[1]); // 列数

// 读取第二行输入，分割成字符串数组并解析为起点和终点的坐标
        String[] strB = br.readLine().trim().split("\\s+");
        int xs = Integer.parseInt(strB[0]) -
                 1; // 起点x坐标（转换为0-based索引）
        int ys = Integer.parseInt(strB[1]) -
                 1; // 起点y坐标（转换为0-based索引）
        int xt = Integer.parseInt(strB[2]) -
                 1; // 终点x坐标（转换为0-based索引）
        int yt = Integer.parseInt(strB[3]) -
                 1; // 终点y坐标（转换为0-based索引）

// 读取n行输入，构建二维字符数组grid表示地图
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = br.readLine().trim().toCharArray();
        }


// 调用BFS方法计算最短路径长度，并将结果输出
        out.println(bfs(grid, n, m, xs, ys, xt, yt));
// 刷新输出流，确保所有内容都被写出
        out.flush();
// 关闭输出流和输入流
        out.close();
        br.close();

    }

    /**
    * 使用广度优先搜索(BFS)算法计算从起点到终点的最短路径
    *
    * @param grid 二维字符数组，表示网格地图，'.'表示可走的路径
    * @param n 网格的行数
    * @param m 网格的列数
    * @param xs 起点的x坐标
    * @param ys 起点的y坐标
    * @param xt 终点的x坐标
    * @param yt 终点的y坐标
    * @return 从起点到终点的最短距离，如果无法到达则返回-1
    */
    private static int bfs(char[][] grid, int n, int m, int xs, int ys, int xt,
                           int yt) {
// 如果起点和终点相同，直接返回0
        if (xs == xt && ys == yt) {
            return 0;
        }

// 初始化距离数组，-1表示未访问过
        int[][] distance = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(distance[i], -1);
        }

// 使用队列实现BFS，存储待访问的节点坐标
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {xs, ys});
        distance[xs][ys] = 0; // 起点到自身的距离为0

// 定义四个方向的偏移量，分别表示上、下、左、右
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

// BFS遍历
        while (!queue.isEmpty()) {
// 取出队列中的当前节点
            int[] cur = queue.poll();

            int x = cur[0];
            int y = cur[1];

// 遍历四个方向
            for (int i = 0; i < 4; i++) {
// 计算下一个节点的坐标
                int nextX = x + dx[i];
                int nextY = y + dy[i];

// 检查下一个节点是否在网格范围内，且是可走的路径，且未被访问过
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m &&
                        grid[nextX][nextY] == '.' && distance[nextX][nextY] == -1) {
// 更新距离
                    distance[nextX][nextY] = distance[x][y] + 1;

// 如果到达终点，返回距离
                    if (nextX == xt && nextY == yt) {
                        return distance[nextX][nextY];
                    }

// 将下一个节点加入队列
                    queue.add(new int[] {nextX, nextY});
                }
            }
        }
// 如果无法到达终点，返回-1
        return -1;
    }
}