注:数对可通过javafx.util.Pair实现,但acwing不支持,可以自己用泛型手动实现一个简单的。
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class BFSMaze {
static final int N = 110;
static int[][] maze = new int[N][N]; //迷宫
static int[][] dist = new int[N][N]; //每个点到终点的距离
static Queue<Pairs<Integer,Integer>> queue = new LinkedList<>();
static int n;
static int m;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = reader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
for (int i = 0; i < n; i++) {
s = reader.readLine().split(" ");
for (int j = 0; j < m; j++) { //初始化迷宫
maze[i][j] = Integer.parseInt(s[j]);
}
}
for(int i = 0; i < n; i++) { //初始化距离,-1表示未探索或不可到达
Arrays.fill(dist[i],0,m,-1);
}
log.write(bfs() +"");
log.flush();
log.close();
reader.close();
}
private static int bfs() {
int[] dx = {-1,0,1,0}; int[] dy = {0,1,0,-1}; //四个方向的优先级为左上右下
//初始化
queue.add(new Pairs<>(0, 0));
dist[0][0] = 0;
//若队列不为空,循环出列并扩展
while (!queue.isEmpty()) {
Pairs<Integer,Integer> Pairs = queue.remove();
for (int i = 0; i < 4; i++) { //四个方向扩展,若合乎条件就入列
int x = Pairs.getKey() +dx[i];
int y = Pairs.getValue() +dy[i];
if(x >= 0 && x < n && y>=0 && y < m && maze[x][y] == 0 && dist[x][y] == -1) {
dist[x][y] = dist[Pairs.getKey()][Pairs.getValue()] + 1; //距离为上一层+1
queue.add(new Pairs<>(x, y));
}
}
}
return dist[n-1][m-1];
}
}
class Pairs<T1, T2> {
private T1 key;
private T2 value;
public Pairs(T1 t1,T2 t2) {
key = t1;
value = t2;
}
public T1 getKey() {
return key;
}
public T2 getValue() {
return value;
}
}