【蓝桥杯】走迷宫
题目：https://i-blog.csdnimg.cn/direct/314ac8f01e3f4b74b2394aaa35c3f076.png解题思路：
简朴的广度优先算法（BFS）
BFS 的特性
[*]按层次遍历：BFS 按照节点的间隔（边的数量）来逐层访问节点。
[*]包管最短路径：对于无权图（所有边权重相同），BFS 能够找到从起点到任何其他节点的最短路径。
[*]避免回路：通过使用已访问标志（visited 数组），可以防止重复访问同一个节点，从而避免无限循环。
[*]队列结构：使用队列来管理待访问的节点。
import java.util.Scanner;
import java.util.Queue;
import java.util.ArrayDeque;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
//方向
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
//标记是否走过
static boolean[][] visted;
//矩阵大小
static int N, M;
//入口、出口位置
static int startx, starty, endx, endy;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
N = scan.nextInt();
M = scan.nextInt();
int [][] arr = new int;
visted = new boolean;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
arr = scan.nextInt();
}
}
startx = scan.nextInt();
starty = scan.nextInt();
endx = scan.nextInt();
endy = scan.nextInt();
System.out.println(bfs(arr, startx - 1, starty - 1));
scan.close();
}
public static int bfs(int[][] arr, int x, int y) {
//创建队列，更新位置
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[] {x, y, 0});
while(!q.isEmpty()) {
int[] poll = q.poll();
int x1 = poll;
int y1 = poll;
int steps = poll;
//判断是否到达终点
if (x1 == endx-1 && y1 == endy-1) {
return steps;
}
//根据四个方向走下一步
for (int i = 0; i < 4; i++) {
int xx = x1 + dx;
int yy = y1 + dy;
if (xx >=0 && yy >= 0 && xx < N && yy < M && !visted && arr == 1) {
visted = true;
q.offer(new int[] {xx, yy, steps + 1});
}
}
}
return -1;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]