經典算法50例 老鼠走迷宮1，2

本文來源和參考于經典算法50例。隻不過把c換成java來實作。

老鼠走迷官（一）

說明

老鼠走迷宮是遞回求解的基本題型，我們在二維陣列中使用2表示迷宮牆壁，使用1來表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。

解法

老鼠的走法有上、左、下、右四個方向，在每前進一格之後就選一個方向前進，無法前進時退回選擇下一個可前進方向，如此在陣列中依序測試四個方向，直到走到出口為止，這是遞回的基本題，請直接看程式應就可以了解。

public  static int[][]  maze={{2, 2, 2, 2, 2, 2, 2},
            {2, 0, 0, 0, 0, 0, 2},
            {2, 0, 2, 0, 2, 0, 2},
            {2, 0, 0, 2, 0, 2, 2},
            {2, 2, 0, 2, 0, 2, 2},
            {2, 0, 0, 0, 0, 0, 2},
            {2, 2, 2, 2, 2, 2, 2}};

    public static int success=0;

    public static void main(String[] args) {

        System.out.println("顯示迷宮：");
        for (int i = 0; i <7 ; i++) {
            for (int j = 0; j < 7; j++) {
                if(maze[i][j]==2){
                    System.out.print("■");
                }else if(maze[i][j]==0){
                    System.out.print("□");
                }
            }
            System.out.println(" ");
        }

        int starti=1,startj=1;//1，1為入口。
        visit(starti,startj);
        if(success==0){
            System.out.println("沒有找到出口");
        }else {
            System.out.println("正确路線為○");
            for (int i = 0; i <7 ; i++) {
                for (int j = 0; j < 7; j++) {
                    if(maze[i][j]==2){
                        System.out.print("■");
                    }else if(maze[i][j]==0){
                        System.out.print("□");
                    }else if(maze[i][j]==1){
                        System.out.print("○");
                    }
                }
                System.out.println(" ");
            }
        }
    }


    public static int visit(int i,int j){
        int endi=5,endj=5;

        maze[i][j]=1;
        if(i==endi&&j==endj){
            success=1;
        }

        if(success!=1&&maze[i][j+1]==0) visit(i,j+1);
        if(success!=1&&maze[i+1][j]==0) visit(i+1,j);
        if(success!=1&&maze[i-1][j]==0) visit(i-1,j);
        if(success!=1&&maze[i][j-1]==0) visit(i,j-1);
        if (success!=1)
            maze[i][j]=0;

       return success;
    }
           

老鼠走迷官（二）

說明

由于迷宮的設計，老鼠走迷宮的入口至出口路徑可能不隻一條，如何求出所有的路徑呢？

解法

求所有路徑看起來複雜但其實更簡單，隻要在老鼠走至出口時顯示經過的路徑，然後退回上一格重新選擇下一個位置繼續遞回就可以了，比求出單一路徑還簡單，我們的程式隻要作一點修改就可以了。

public  static int[][]  maze=
            {{2, 2, 2, 2, 2, 2, 2, 2, 2},
            {2, 0, 0, 0, 0, 0, 0, 0, 2},
            {2, 0, 2, 2, 0, 2, 2, 0, 2},
            {2, 0, 2, 0, 0, 2, 0, 0, 2},
            {2, 0, 2, 0, 2, 0, 2, 0, 2},
            {2, 0, 0, 0, 0, 0, 2, 0, 2},
            {2, 2, 0, 2, 2, 0, 2, 2, 2},
            {2, 0, 0, 0, 0, 0, 0, 0, 2},
            {2, 2, 2, 2, 2, 2, 2, 2, 2}};

    public static int starti=1,startj=1;
    public static int endi=7,endj=7;
   public static int num=0;

    public static void main(String[] args) {
            show();
            visit(1,1);
    }

    public static void show(){
        System.out.println("顯示迷宮："+num);
        for (int i = 0; i <9 ; i++) {
            for (int j = 0; j < 9; j++) {
                if(i==starti&&j==startj) {
                    System.out.print("△");
                }else if(i==endi&&j==endj){
                    System.out.print("☆");
                }else if(maze[i][j]==2){
                        System.out.print("■");
                }else if(maze[i][j]==0){
                        System.out.print("□");
                }else {
                        System.out.print("○");
                }
            }
            System.out.println(" ");
        }
    }

    public static void visit(int i,int j){

        maze[i][j] = 1;

        if(i==endi&&j==endj){
            num++;
            show();
        }

        if(maze[i][j+1]==0) visit(i,j+1);
        if(maze[i+1][j]==0) visit(i+1,j);
        if(maze[i-1][j]==0) visit(i-1,j);
        if(maze[i][j-1]==0) visit(i,j-1);
            maze[i][j]=0;

    }