经典算法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;

    }