AcWing 844. 走迷宫---Java
原题链接
简单
作者:
夏日的小提琴
,
2021-10-28 11:02:48
,
所有人可见
,
阅读 180
import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
public class Main {
static int n, m;
static int[][] g;//存储地图信息(0可走,1不可走)
static int[][] d;//存储走到该点的最小次数
static int[] dx = {-1, 0, 1, 0};//上,右,下,左 的坐标
static int[] dy = {0, 1, 0, -1};
static Deque<int[]> queue = new LinkedList<>();
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] str = reader.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
g = new int[n][m];
d = new int[n][m];
for (int i = 0; i < n; i++) {
String[] str1 = reader.readLine().split(" ");
for (int j = 0; j < m; j++) {
g[i][j] = Integer.parseInt(str1[j]);
d[i][j] = -1;//初始化为-1表示,该格子还未走过
}
}
d[0][0] = 0;//表示出发点初始步数从0开始
writer.write(bfs() + "");
writer.flush();
writer.close();
reader.close();
}
public static int bfs() {
queue.offer(new int[]{0, 0});//先将出发点坐标放入队列
while (!queue.isEmpty()) {
int[] loc = queue.poll();//队头出队
for (int i = 0; i < 4; i++) {//遍历周围四个方向,哪个能走,就把哪个加入队列,即广搜的思想
int x = loc[0] + dx[i];
int y = loc[1] + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {//满足这些条件才表示该方向是可走的
d[x][y] = d[loc[0]][loc[1]] + 1;//如果该方向能走,则步数加一
queue.offer(new int[]{x, y});//将可以走的格子加入队列
}
}
}
return d[n - 1][m - 1];
}
}