AcWing 844. 走迷宫
原题链接
简单
作者:
不酸柠檬柚
,
2024-03-26 23:49:44
,
所有人可见
,
阅读 2
题目描述
走迷宫
经典BFS模板题
样例
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
8
java 代码
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
//构造节点
static class node{
public int x;
public int y;
public node(int x, int y){
this.x = x;
this.y = y;
}
}
static int[][] vis = new int[110][110]; //存储是否访问过,并且存储长度
static int[][] G = new int[110][110]; //存储给我们的地图
static int n, m, res;
static node State, End;
static Queue<node> q = new ArrayDeque<>();
//构造方向
static int[] dx = {0,1,-1,0};
static int[] dy = {1,0,0,-1};
//判断
static boolean PD(int x, int y){
if (x < 1)
return false;
else if (x > n)
return false;
else if (y < 1)
return false;
else if (y > m)
return false;
else if (vis[x][y] != 0)
return false;
//已经走过了
else if (G[x][y] != 0)
//遇到障碍物了
return false;
return true;
}
static boolean check(int x, int y){
if (End.x == x && End.y == y){
res = vis[x][y];
return true;
}else
return false;
}
static void BFS(){
q.add(State); // 将起点加入队列
vis[State.x][State.y] = 1; // 标记起点已访问
node now, next; // 定义当前节点和下一个节点
while (q.size() != 0){ // 当队列非空时循环
now = q.peek(); // 获取队头元素(当前节点)
if (check(now.x, now.y)) // 检查当前节点是否为目标节点
return; // 如果是目标节点,结束搜索
q.poll(); // 出队,移除当前节点
// 遍历当前节点的四个相邻节点
for (int i = 0; i < 4; i++) {
int nextx = now.x + dx[i]; // 计算相邻节点的横坐标
int nexty = now.y + dy[i]; // 计算相邻节点的纵坐标
if (PD(nextx,nexty)){ // 判断相邻节点是否合法
next = new node(nextx,nexty); // 创建相邻节点对象
q.add(next); // 将相邻节点加入队列
vis[nextx][nexty] = vis[now.x][now.y] + 1; // 更新相邻节点的访问标记为当前节点的访问标记加一(表示路径长度加一)
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
G[i][j] = sc.nextInt();
}
}
State = new node(1,1);
End = new node(n,m);
BFS();
System.out.println(res - 1);
}
}