【蓝桥杯】走迷宫

题目：

解题思路：

        简单的广度优先算法（BFS）

BFS 的特性

1. 按层次遍历：BFS 按照节点的距离（边的数量）来逐层访问节点。
2. 保证最短路径：对于无权图（所有边权重相同），BFS 能够找到从起点到任何其他节点的最短路径。
3. 避免回路：通过使用已访问标记（visited 数组），可以防止重复访问同一个节点，从而避免无限循环。
4. 队列结构：使用队列来管理待访问的节点。

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[N][M];visted = new boolean[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {arr[i][j] = 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[0];int y1 = poll[1];int steps = poll[2];//判断是否到达终点if (x1 == endx-1 && y1 == endy-1) {return steps;}//根据四个方向走下一步for (int i = 0; i < 4; i++) {int xx = x1 + dx[i];int yy = y1 + dy[i];if (xx >=0 && yy >= 0 && xx < N && yy < M && !visted[xx][yy] && arr[xx][yy] == 1) {visted[xx][yy] = true;q.offer(new int[] {xx, yy, steps + 1});}}}return -1;}
}