题解 | #走迷宫#

为你的题解加了注释： import java.util.*; /** * 这个程序计算在一个二维网格中从起点到终点的最短步数。 * 网格中的每个单元格可以是空格（'.'）、障碍物（'*'）或已经走过的路径（'/'）。 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 创建一个扫描器对象用于输入 // 读取第一行输入，获取网格的行数（n）和列数（m） String[] s1 = sc.nextLine().split(" "); int n = Integer.parseInt(s1[0]); // 行数 int m = Integer.parseInt(s1[1]); // 列数 // 读取第二行输入，获取起点和终点的坐标 String[] s2 = sc.nextLine().split(" "); int sti = Integer.parseInt(s2[0]); // 起点行坐标 int stj = Integer.parseInt(s2[1]); // 起点列坐标 int ovi = Integer.parseInt(s2[2]); // 终点行坐标 int ovj = Integer.parseInt(s2[3]); // 终点列坐标 // 初始化字符数组表示网格 char[][] grid = new char[n][m]; // 逐行读取输入并填充网格数组 for (int i = 0; i < n; i++) { String s = sc.nextLine(); for (int j = 0; j < m; j++) { grid[i][j] = s.charAt(j); } } // 检查起点和终点是否有障碍物 if (grid[sti - 1][stj - 1] == '*' || grid[ovi - 1][ovj - 1] == '*') { System.out.println(-1); // 如果起点或终点有障碍物，则无法到达 return; } // 创建队列用于广度优先搜索（BFS） Queue<int> queue = new LinkedList<>(); // 将起点加入队列，并初始化步数为0 int[] node = {0, sti - 1, stj - 1}; queue.offer(node); // 调用方法计算最短步数 int result = minStep(n, m, grid, ovi - 1, ovj - 1, queue); // 输出结果 System.out.println(result); } /** * 使用广度优先搜索算法计算从起点到终点的最短步数。 * * @param n 网格的行数 * @param m 网格的列数 * @param arr 网格数组 * @param ovi 终点行坐标 * @param ovj 终点列坐标 * @param queue 用于BFS的队列 * @return 最短步数或-1如果无法到达 */ public static int minStep(int n, int m, char[][] arr, int ovi, int ovj, Queue<int> queue) { // BFS主循环 while (queue.size() != 0) { // 取出队列中的第一个节点 int[] node = queue.poll(); int step = node[0]; // 当前步数 int i = node[1]; // 当前行坐标 int j = node[2]; // 当前列坐标 // 如果当前节点是终点，则返回步数 if (i == ovi && j == ovj) { return step; } // 向右移动 if (j + 1 < m && arr[i][j + 1] == '.') { int[] node1 = {step + 1, i, j + 1}; queue.offer(node1); arr[i][j + 1] = '/'; // 标记已走过的路径 } // 向下移动 if (i + 1 < n && arr[i + 1][j] == '.') { int[] node1 = {step + 1, i + 1, j}; queue.offer(node1); arr[i + 1][j] = '/'; // 标记已走过的路径 } // 向左移动 if (j - 1 >= 0 && arr[i][j - 1] == '.') { int[] node1 = {step + 1, i, j - 1}; queue.offer(node1); arr[i][j - 1] = '/'; // 标记已走过的路径 } // 向上移动 if (i - 1 >= 0 && arr[i - 1][j] == '.') { int[] node1 = {step + 1, i - 1, j}; queue.offer(node1); arr[i - 1][j] = '/'; // 标记已走过的路径 } } // 如果无法到达终点，返回-1 return -1; } }</int></int>