AcWing 844. 走迷宫Java详细理解(无需编写队列)
原题链接
简单
作者:
crayon不小心
,
2021-02-01 21:26:37
,
所有人可见
,
阅读 582
import java.util.*;
public class Main {
static final int N = 110;
static int [][] s = new int[N][N];
static int [][] d = new int[N][N];
static int m,n;
//JAVA 中通过调用类AbstractMap下的SimpleEntry方法构建简单的存放二维坐标的队列,此方法可以不通过给定迭代器直接获取键值对
static Queue<AbstractMap.SimpleEntry<Integer,Integer>> queue = new ArrayDeque<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
s[i][j] = sc.nextInt();
}
}
//未访问的点置为 -1
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = -1;
}
}
//开始点,置为 0
d[0][0] = 0;
System.out.println(bfs());
}
public static int bfs()
{
//将坐标 (0,0) 放进队列中,用作取值计算偏移量
queue.add(new AbstractMap.SimpleEntry<>(0,0));
//定义偏移量
int [] dx = {-1, 0, 1, 0};
int [] dy = {0 ,1, 0, -1};
//d[x][y] 即为第一次到达该点的距离,由于是第一次到达,即为到达某点(x,y)的最短路径
while (!queue.isEmpty())
{
//将队列中第一个元素取出,计算偏移后的目标点
AbstractMap.SimpleEntry<Integer, Integer> remove = queue.remove();
for (int i = 0; i < 4; i++) {
int sx = dx[i] + remove.getKey(), sy = dy[i] + remove.getValue();
if (sx >= 0 && sx < m && sy >=0 && sy < n && s[sx][sy] == 0 && d[sx][sy] == -1) {
//当一个点找到,就标记这个点的值为从起点到达该点的距离,其为最短距离
//由于偏移量的最小单位为1,每次距离加1
d[sx][sy] = d[remove.getKey()][remove.getValue()] + 1;
queue.add(new AbstractMap.SimpleEntry<>(sx, sy));
}
}
}
return d[m - 1][n - 1];
}
}
这个queue的写法是Jdk1.8的嘛?