1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
/**
* 主方法，处理输入输出并调用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;
}
|
