【蓝桥杯】走迷宫

题目：

解题思路：

        简朴的广度优先算法（BFS）
BFS 的特性

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

1. import java.util.Scanner;
2. import java.util.Queue;
3. import java.util.ArrayDeque;
4. // 1:无需package
5. // 2: 类名必须Main, 不可修改
7. public class Main {
8.   //方向
9.   static int[] dx = {0, 0, -1, 1};
10.   static int[] dy = {1, -1, 0, 0};
11.   //标记是否走过
12.   static boolean[][] visted;
13.   //矩阵大小
14.   static int N, M;
15.   //入口、出口位置
16.   static int startx, starty, endx, endy;
17.   public static void main(String[] args) {
18.       Scanner scan = new Scanner(System.in);
19.       //在此输入您的代码...
20.       N = scan.nextInt();
21.       M = scan.nextInt();
22.       int [][] arr = new int[N][M];
23.       visted = new boolean[N][M];
24.       for (int i = 0; i < N; i++) {
25.         for (int j = 0; j < M; j++) {
26.           arr[i][j] = scan.nextInt();
27.         }
28.       }
29.       startx = scan.nextInt();
30.       starty = scan.nextInt();
31.       endx = scan.nextInt();
32.       endy = scan.nextInt();
33.       System.out.println(bfs(arr, startx - 1, starty - 1));
34.       scan.close();
35.   }
36.   public static int bfs(int[][] arr, int x, int y) {
37.     //创建队列，更新位置
38.     Queue<int[]> q = new ArrayDeque<>();
39.     q.offer(new int[] {x, y, 0});
41.     while(!q.isEmpty()) {
42.       int[] poll = q.poll();
43.       int x1 = poll[0];
44.       int y1 = poll[1];
45.       int steps = poll[2];
46.       //判断是否到达终点
47.       if (x1 == endx-1 && y1 == endy-1) {
48.         return steps;
49.       }
50.       //根据四个方向走下一步
51.       for (int i = 0; i < 4; i++) {
52.         int xx = x1 + dx[i];
53.         int yy = y1 + dy[i];
54.         if (xx >=0 && yy >= 0 && xx < N && yy < M && !visted[xx][yy] && arr[xx][yy] == 1) {
55.           visted[xx][yy] = true;
56.           q.offer(new int[] {xx, yy, steps + 1});
57.         }
58.       }
59.     }
60.     return -1;
61.   }
62. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。