import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class P {
int x;
int y;
public P(int a, int b) {
this.x = a;
this.y = b;
}
}
public class Main {
static final int INF = -1;
static char[][] arr;
static int[][] dis;
static int[] tempx = { 1, 0, -1, 0 };
static int[] tempy = { 0, 1, 0, -1 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int sx = 0, sy = 0, gx = 0, gy = 0;
arr = new char[N][M];
dis = new int[N][M];
for (int i = 0; i < N; i++) { // 输入 以及得到sx sy 的地址
String str = sc.next();
arr[i] = str.toCharArray();
for (int x = 0; x < str.length(); x++) {
dis[i][x] = INF; // 把所有位置初始化为INF 初始化
if (str.charAt(x) == 'S') {
sx = i;
sy = x;
}
if (str.charAt(x) == 'G') {
gx = i;
gy = x;
}
}
}
dis[sx][sy] = 0; //将起点设置为 0
Queue<P> que = new LinkedList<P>(); //创建一个队列
que.offer(new P(sx, sy)); //直接扔到队列里面
// System.out.println(sx + " " + sy + " " + gx + " " + gy);
while (que.size() > 0) {
P p = que.poll(); //poll队列的头
if (p.x == gx && p.y == gy) //到达终点跳出来
break;
for (int i = 0; i < 4; i++) { //四个方向
int nx = p.x + tempx[i];
int ny = p.y + tempy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < M && dis[nx][ny] == INF && arr[nx][ny] != '#') {
que.offer(new P(nx, ny));
dis[nx][ny] = dis[p.x][p.y] + 1;
}
}
}
System.out.println(dis[gx][gy]);
}
}
迷宫的最短路径--BFS
程序员文章站
2023-12-24 13:21:27
...