蓝桥杯2019Java组省赛填空题—迷宫（BFS+IO流）

👉🏻题目链接：

🚀https://www.lanqiao.cn/problems/602/learning/🚀

程序填空—迷宫：

⭐⭐⭐

010101010010110010010101100101101001000010001010100000100010000010101001000010000000100110011010010101111011010010001000001101001011100011000000010000010000000010101000110100001010000010101010110010110001111100000010100001001010001010000010110000000011001000110101000010101100011010011010101011110111000110110101010010010010100000010001010011100000001010000010100010011010101011111001100001000011101000111000001010100001100010000001000101001100001001110001101000011100100010010101010101010100011010000001000010010000010100101010111010001010101000010111100100101001001000010000010101010100100100010100000000100000001010110011110100011000001010101000111010101001110000100001100001011001111011010000100010101010100001101010100101000010100000111011101001100000001011000100001011001011010010111000000001001010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000

⭐⭐⭐

• 迷宫问题可以使用Excel大法，将迷宫复制到表格中手动走一遍。
• 如果是常规解法这道题主要考察JavaIO与BFS的模板。
• 用DFS走迷宫运行时间很长，跑不出来；而且题目要求迷宫的解要满足字典序最小，使用BFS更方便。题目属于简单题，在BFS模板的基础上设置好行走顺序，跑一遍模板就ok了。
  BFS模板可以参考这篇文章：
  【蓝桥杯Java组】刷了这五道题不信你还不会BFS（广度优先搜索）
• 30行50列的迷宫如果手动输入大概率会出错，需要从txt文本文件中使用IO流读数据。

🍦AC代码（Java）：

import java.io.File;import java.io.FileReader;import java.io.IOException;import java.util.Deque;import java.util.LinkedList;//结点用来记录状态class Node {//    坐标    int x;    int y;//    走迷宫的路径    StringBuilder path;    Node(int x, int y, StringBuilder path) { this.x = x; this.y = y; this.path = path;    }}public class Main {    public static final int n = 30;    public static final int m = 50;    public static char[][] maze = new char[n][m];    public static boolean[][] vis = new boolean[n][m];//    按照字典序设置行走顺序    public static int[][] dir = new int[][]{     {1, 0}, {0, -1}, {0, 1}, {-1, 0}    };    public static char[] go = new char[]{'D', 'L', 'R', 'U'};    public static boolean inMaze(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m;    }//    bfs模板，方法结束时就是最短路径，根据设置的顺序走，路径字典序也为最小    public static String bfs(int sx, int sy) { Deque<Node> que = new LinkedList<>(); que.add(new Node(sx, sy, new StringBuilder(""))); vis[sx][sy] = true; while (!que.isEmpty()) {     Node curr = que.pop();     if (curr.x == n - 1 && curr.y == m - 1) {  return curr.path.toString();     }//     尝试向四个方向走，并记录路径     for (int i = 0; i < 4; i++) {  int tx = curr.x + dir[i][0];  int ty = curr.y + dir[i][1];  if (inMaze(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '1') {      vis[tx][ty] = true;//      这里千万不要写成StringBuilder tempPath = curr.path//      Java中这样写，tempPath指向的一直是是内存中同一个字符串      StringBuilder tempPath = new StringBuilder(curr.path);      tempPath.append(go[i]);      que.offer(new Node(tx, ty, tempPath));  }     } } return "";    }    public static void main(String[] args) throws IOException {// 通过IO读取题目样例 File file = new File("E:\\test.txt"); FileReader fr = new FileReader(file); for (int i = 0; i < 30; i++) {     for (int j = 0; j <= 51; j++) {  int ch = fr.read();  //  处理每行末尾的换行，Windows下换行符是/r/n，要读取两次  if (j == 50 || j == 51)      continue;  maze[i][j] = (char) ch;     } } String ans = bfs(0, 0); System.out.println(ans);    }}

✨结果：✨

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR