有问题没想通:等我明天
参考文献:
/ 1,y总代码
* 2,CSDN博主「戏子zzz」
* 原文链接:https://blog.csdn.net/weixin_45480785/article/details/113063968
* 3,作者:lkm
* 链接:https://www.acwing.com/solution/content/19735/
/
代码部分:
//BFS
//走迷宫
package java003;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main2 {
static int N=110;
static int n, m;
static int[][] g= new int[N][N];//存储地图
static int[][] d= new int[N][N];//每个点到起点的距离
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
g[i][j] = sc.nextInt();
}
}
System.out.println(bfs());
}
private static int bfs() {
Queue<int[]> queue=new LinkedList<>();//定义一个队列
int[] dx= {-1,0,1,0},dy= {0,1,0,-1};
queue.offer(new int[] {0,0});//记录起始位置
int x=0,y=0;
while(!queue.isEmpty()) {
int[] poll = queue.poll();
x=poll[0];
y=poll[1];
for(int i=0;i<4;i++) {//该点往四个方向突围,寻找最短路
int a=x+dx[i];
int b=y+dy[i];
if(a>=0 && a<n&&b>=0&& b<m && g[a][b]==0&& d[a][b]==0) {
//在边界,并且点是空地,并且点还没用
queue.offer(new int[] {a,b});//存在,记录该点
d[a][b]=d[x][y]+1;//继续走下一个位置
}
}
}
return d[n - 1][m - 1];
}
}