Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

內容：

A4 逃離迷宮

使用讀檔方式讀入一個 15*15 的迷宮，程式負責計劃逃出路線，並使用寫檔方式輸出有逃離路線的地圖檔 ( s學號.txt )

 

迷宮範例： maze.txt

能走為 0，牆壁為 1，左上角為入口、右下角為出口，可以走斜的 (即必須考慮八個方向)

 

輸入：
迷宮檔案路徑 ( ex: C:\Users\wayne\workspace\ce1002-A\src\ce1002\A4\s101522071\maze.txt )

輸出：
s學號.txt

 

輸出路徑請使用這行： java.io.File write_file = new java.io.File( “s學號.txt” );

這樣輸出的檔案會在： C:\Users\Wayne\workspace\ce1002-A\s101522071.txt

 

執行結果：

請輸入一個 15*15 的迷宮: (能走為 0 ,牆壁為 1)                      --( 規定:左上角[0][0]為入口, 右下角[14][14]為出口, 其餘邊緣皆是牆壁 )    |--> 這些都要顯示＊注意:測出路線之後,已走過路線會被記為2,若是死路則記為4                --請輸入要讀取的檔案路徑 (例: c:\maze.txt): C:\Users\Wayne\Desktop\maze.txt  ---> 路徑為使用者輸入您的迷宮為:011111111111111100000011111111110111111111111110111000000011110001011011011110110010111011110111111011111110111000011111101100111101111100101111100011111110101110111111110010111111110011011000111111000011110001111111111111110---路線已畫出: s101522071.txt---

執行輸出：(檔案中)
211111111111111
120000011111111
112111111111111
112111022000011
110221211211011
110112012111011
110111111211111
110111222011111
101102111101111
100121111100011
111112121110111
111110212111111
110011011222111
111000011110221
111111111111112

---

助教提示要用 stack, 或者使用內建的 class Stack.

個人覺得如果使用 recursion 去解, 呼叫 void dfs(int x, int y) 是很容易寫的，
而在全區放一個變數用以標記死路操作的 boolean。

如果不想輸出死路，一路到底的話，還是建議使用 bfs 拓展，然後從終點回溯標記，
如此一來不會出現死路，但也不打算使用 class Queue, 太多餘了, 不使用.

如果在演算法上還要更快的話, 使用 A* algorithm, 但需要一個 priority queue 支持。
效率上很不錯的, 這作業就不想這麼改寫了, 有興趣的可以去查一下,
ZJ 也有一題我出的 "迷宮路徑".

覺得我沒救了，在爭奪一個題目要求輸出一條迷宮的逃離路徑，
首先題目只有說明要規劃逃離路徑，接著用指定符號標示逃離。
不懂死路標記的用意，如果能找到一條路徑抵達終點，其實是
沒有必要的，如果題目說明一定要以模擬的角度去寫，那麼使
用堆疊模擬是必要的。
-----
使用 BFS + 回溯追蹤的方法可以找到最短路徑，且輸出其一走
法，但是這做法跟標記無關，壓根不用想那種事情，如果死路
標記是這麼定義：找到地圖上的缺口，而這個缺口是無法抵達
終點，則將之後的連通子圖以指定符號填滿。ACM 寫多的時候
，真的會讓人對於輸出執著。

於是，我還是把 DFS 的做法補上了，反正也不到三十行。

package ce1002.A4.s100502205;

import java.util.Scanner;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.io.File;

public class A4 {
    private static final int HEIGHT = 15;
    private static final int WIDTH = 15;

    static boolean dfs(int x, int y, char[][] map) {
        map[x][y] = '2';
        if (x == HEIGHT - 1 && y == WIDTH - 1) // end_x end_y;
            return true;
        boolean argv = false;
        for (int i = 1; i >= -1; i--) {
            for (int j = 1; j >= -1; j--) {
                int tx = x + i, ty = y + j;
                if (tx < 0 || ty < 0 || tx >= HEIGHT || ty >= WIDTH)
                    continue;
                if (map[tx][ty] == '0') {
                    argv = dfs(tx, ty, map);
                    if (argv)
                        return true;
                }
            }
        }
        map[x][y] = '4';
        return false;
    }

    static void bfs(char[][] map) {
        int[] Qx = new int[HEIGHT * WIDTH + 5], Qy = new int[HEIGHT * WIDTH + 5];
        int[][] stepRecord = new int[HEIGHT][WIDTH]; // initialize all zero
        int Qt = 0;
        Qx[Qt] = 0;
        Qy[Qt] = 0;
        stepRecord[0][0] = 1;
        for (int i = 0; i <= Qt; i++) {
            int x = Qx[i], y = Qy[i];
            for (int j = -1; j <= 1; j++) {
                for (int k = -1; k <= 1; k++) {
                    int tx = x + j, ty = y + k;
                    if (tx < 0 || ty < 0 || tx >= HEIGHT || ty >= WIDTH)
                        continue;
                    if (map[tx][ty] == '1' || stepRecord[tx][ty] != 0)
                        continue;
                    stepRecord[tx][ty] = stepRecord[x][y] + 1;
                    Qx[++Qt] = tx;
                    Qy[Qt] = ty;
                }
            }
            if (stepRecord[HEIGHT - 1][WIDTH - 1] != 0)
                break;
        }
        int px = HEIGHT - 1, py = WIDTH - 1;
        map[px][py] = '2';
        while (px != 0 || py != 0) {
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    int tx = px + i, ty = py + j;
                    if (tx < 0 || ty < 0 || tx >= HEIGHT || ty >= WIDTH)
                        continue;
                    if (stepRecord[tx][ty] == stepRecord[px][py] - 1) {
                        px = tx;
                        py = ty;
                        i = 2;
                        j = 2;
                    }
                }
            }
            map[px][py] = '2';
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        Scanner fin = null;
        PrintStream fout = null;
        File writeFile = new File("s100502205.txt");
        File readFile = null;
        char[][] map = new char[HEIGHT][];
        System.out.println("請輸入一個 15*15 的迷宮: (能走為 0 ,牆壁為 1)");
        System.out.println("( 規定:左上角[0][0]為入口, 右下角[14][14]為出口, 其餘邊緣皆是牆壁 )");
        System.out.println("＊注意:測出路線之後,已走過路線會被記為2,若是死路則記為4");
        System.out.print("請輸入要讀取的檔案路徑 (例: c:\\maze.txt): ");
        try {
            readFile = new File(cin.next());
            fin = new Scanner(new FileInputStream(readFile));
            fout = new PrintStream(new FileOutputStream(writeFile));
            System.out.println("\n您的迷宮為:");
            int row = 0;
            while (fin.hasNext()) {
                map[row] = fin.next().toCharArray();
                System.out.println(map[row]);
                if (map[row].length != WIDTH)
                    throw new Exception("Number of column Error!");
                row++;
            }
            if (row != HEIGHT)
                throw new Exception("Number of row Error!");
        } catch (Exception e) {
            System.out.println(e.getMessage());
            System.exit(0);
        }
        //bfs(map);
        dfs(0, 0, map); //(start_x, start_y, map_info);
        for (int i = 0; i < HEIGHT; i++)
            fout.println(map[i]);
        System.out.println("\n---路線已畫出: s100502205.txt---");
        fin.close();
        fout.close();
    }
}