2019 第十屆 藍橋杯 JavaB組 省賽E題迷宮(bfs）

下圖給出了一個迷宮的平面圖，其中标記為 1 的為障礙，标記為 0 的為可

以通行的地方。

010000

000100

001001

110000

迷宮的入口為左上角，出口為右下角，在迷宮中，隻能從一個位置走到這

個它的上、下、左、右四個方向之一。

對于上面的迷宮，從入口開始，可以按DRRURRDDDR 的順序通過迷宮，

一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

對于下面這個更複雜的迷宮（30 行 50 列），請找出一種通過迷宮的方式，

其使用的步數最少，在步數最少的前提下，請找出字典序最小的一個作為答案。

請注意在字典序中D<L<R<U。（如果你把以下文字複制到文本檔案中，請務

必檢查複制的内容是否與文檔中的一緻。在試題目錄下有一個檔案 maze.txt，

内容與下面的文本相同）

01010101001011001001010110010110100100001000101010

00001000100000101010010000100000001001100110100101

01111011010010001000001101001011100011000000010000

01000000001010100011010000101000001010101011001011

00011111000000101000010010100010100000101100000000

11001000110101000010101100011010011010101011110111

00011011010101001001001010000001000101001110000000

10100000101000100110101010111110011000010000111010

00111000001010100001100010000001000101001100001001

11000110100001110010001001010101010101010001101000

00010000100100000101001010101110100010101010000101

11100100101001001000010000010101010100100100010100

00000010000000101011001111010001100000101010100011

10101010011100001000011000010110011110110100001000

10101010100001101010100101000010100000111011101001

10000000101100010000101100101101001011100000000100

10101001000000010100100001000100000100011110101001

00101001010101101001010100011010101101110000110101

11001010000100001100000010100101000001000111000010

00001000110000110101101000000100101001001000011101

10100101000101000000001110110010110101101010100001

00101000010000110101010000100010001001000100010101

10100001000110010001000010101001010101011111010010

00000100101000000110010100101001000001000000000010

11010000001001110111001001000011101001011011101000

00000110100010001000100000001000011101000000110011

10101000101000100010001111100010101001010000001000

10000010100101001010110000000100101010001011101000

00111100001000010000000110111000000001000000001011

10000001100111010111010001000110111010101101111000

【答案送出】

這是一道結果填空的題，你隻需要算出結果後送出即可。本題的結果為一

個字元串，包含四種字母 D、U、L、R，在送出答案時隻填寫這個字元串，填

寫多餘的内容将無法得分

=============================================================

對于迷宮問題,且是求出最優結果,無疑是要使用廣度優先搜尋(bfs)，因為bfs可齊頭并進(即從不同方向(上下左右)進行搜尋周遊)的方式來對迷宮進行周遊,是以這裡要借助隊列的資料結構,

并且要注意的是題目要求是請找出字典序最小的一個作為答案。請注意在字典序中D<L<R<U。是以在對某一點進行周遊時,要按照該順序來進行周遊搜尋

直接上代碼吧。。。。

class Node{
    int x;
    int y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public Node() {
    }
}
public class Graph {
    //定義方向,由于要字典序最小,既要按D<L<R<U來進行周遊
    static int[] x = {1,0,0,-1};
    static int[] y = {0,-1,1,0};
    //迷宮的長和寬
    static int a=30,b=50;
    //用0和1表示迷宮
    static char[][] arr = new char[a][b];
    //是否該點周遊過
    static int[][] book = new int[a][b];
    //記錄軌迹,存放D,L,R,U
    static char[][] dir = new char[a][b];

    public static void main(String[] args) throws IOException {
        //先将文本内的檔案存入二維數組arr中
        FileReader reader = new FileReader("maze.txt");
        BufferedReader br = new BufferedReader(reader);
        String line;
        int count = 0;
        while ((line=br.readLine())!=null){
            for(int i=0;i<50;i++){
                arr[count][i]=line.charAt(i);
            }
            count++;
        }

        //建立隊列用于存儲線路
        LinkedList<Node> queue = new LinkedList<>();
        //先将起點加入隊列中
        queue.add(new Node(0,0));
        //進行廣度優先搜尋
        bfs(queue);

        //根據記錄的軌迹獲,從終點進行逆推回去即可得到路徑
        int x1=a-1,y1=b-1;
        //由于是從後往前,而其路線是從前往後輸出的,是以這裡需要用到棧來存取
        Stack<Character> stack = new Stack<>();
        while (true){
            //擷取目前的軌迹并壓入棧中
            char d = dir[x1][y1];
            stack.add(d);
            if (d=='U'){//相對于向下
                x1 = x1+1;
            }else if (d=='D'){//相當于向上
                x1 = x1-1;
            }else if (d=='L'){//向右
                y1 = y1+1;
            }else {//向左
                y1 = y1-1;
            }
            //但逆推回地點後即可終止循環
            if (x1==0&&y1==0){
                break;
            }
        }
        //将棧中元素一一彈出即可
        while (stack.size()>0){
            System.out.print(stack.pop());
        }
    }

    private static void bfs(LinkedList<Node> queue) {
        while (queue.size()>0){
            //取出隊列的首元素
            Node temp = new Node();
            temp = queue.pop();
            //将擷取的點設為已通路
            book[temp.x][temp.y]=1;
            for(int i=0;i<4;i++){
                //分别枚舉該點向各個方向的可能,按照題目D<L<R<U來進行枚舉
                int x1 = temp.x + x[i];
                int y1 = temp.y + y[i];
                //要判斷下标是否越界或已到達終點,若該點為1,表示為障礙不能進入,若該點已通路,也跳過
                if (x1<0||y1<0||x1>a-1||y1>b-1||arr[x1][y1]=='1'||book[x1][y1]==1){
                    continue;
                }
                //如果都沒問題表示可以通路改點,将其加入隊列
                book[x1][y1]=1;
                queue.add(new Node(x1,y1));
                //記錄該點的軌迹
                dir[x1][y1]=addDir(i);
            }
        }
    }

    /**
     * 根據i傳回對應的方向
     * @param i
     * @return
     */
    private static char addDir(int i) {
        if (i==0){
            return 'D';
        }else if (i==1){
            return 'L';
        }else if (i==2){
            return 'R';
        }else {
            return 'U';
        }
    }
}
           

輸出的結果如下:

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR