一，走迷宫
1.题目描述：
给定一个 N×MN×M 的网格迷宫 GG。GG 的每个格子要么是道路，要么是障碍物（道路用 11 表示，障碍物用 00 表示）。
已知迷宫的入口位置为 (x1,y1)(x1,y1)，出口位置为 (x2,y2)(x2,y2)。问从入口走到出口，最少要走多少个格子。
2.实例：
输入第 11 行包含两个正整数 N,MN,M，分别表示迷宫的大小。
接下来输入一个 N×MN×M 的矩阵。若 Gi,j=1Gi,j=1 表示其为道路，否则表示其为障碍物。
最后一行输入四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示入口的位置和出口的位置。
1≤N,M≤1021≤N,M≤102，0≤Gi,j≤10≤Gi,j≤1，1≤x1,x2≤N1≤x1,x2≤N，1≤y1,y2≤M1≤y1,y2≤M。
示例 1
输入
5 5
1 0 1 1 0
1 1 0 1 1
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5
输出
83.思路：
输入处理：读取输入数据并转换为迷宫矩阵。
坐标转换：将入口和出口的位置转换为从0开始的索引，方便数组操作。
障碍物检查：直接检查入口和出口是否为障碍物，如果是则立即返回-1。
BFS初始化：使用队列来管理待处理的节点，距离数组记录每个节点的最短步数。
BFS遍历：从入口开始，逐层扩展遍历所有可能的路径，每次处理一个节点时检查其四个方向，更新可达节点的距离并加入队列。找到出口时立即输出结果，否则遍历结束后返回-1。
4：代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] maze = new int[n][m];
// 读取迷宫数据
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
maze[i][j] = scanner.nextInt();
}
}
// 读取起点和终点坐标并转换为0-based索引
int x1 = scanner.nextInt() - 1;
int y1 = scanner.nextInt() - 1;
int x2 = scanner.nextInt() - 1;
int y2 = scanner.nextInt() - 1;
// 检查起点或终点是否为障碍物
if (maze[x1][y1] == 0 || maze[x2][y2] == 0) {
System.out.println(-1);
return;
}
// 处理起点和终点相同的情况
if (x1 == x2 && y1 == y2) {
System.out.println(1);
return;
}
// 初始化距离数组和队列
int[][] dist = new int[n][m];
for (int[] row : dist) {
Arrays.fill(row, -1);
}
dist[x1][y1] = 1;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x1, y1});
// 四个方向移动的增量
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// BFS遍历
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
for (int[] dir : directions) {
int nx = x + dir[0];
int ny = y + dir[1];
// 检查新坐标是否在迷宫范围内
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// 检查是否是道路且未被访问过
if (maze[nx][ny] == 1 && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
// 检查是否到达终点
if (nx == x2 && ny == y2) {
System.out.println(dist[nx][ny]);
return;
}
queue.add(new int[]{nx, ny});
}
}
}
}
// 无法到达终点
System.out.println(-1);
}
}