day6 Java实现自动解迷宫

使用Random随机生成迷宫，
使用递归方法自动解迷宫，
并标出路线和方向。

import java.util.Random;

public class Migong {
    int n = 6;
    int start_X , start_Y , end_X , end_Y ;
    int migong[][];

    public static void main(String[] args) {
        Migong mg = new Migong();
        mg.randomInit();
        System.out.print("start_X=" + mg.start_X + ", start_Y=" + mg.start_Y + "\n");
        System.out.print("end_X=" + mg.end_X + ", end_Y=" + mg.end_Y + "\n");
        System.out.println("Original:");
        mg.printMiGong();
        mg.findWay(mg.migong, mg.start_X, mg.start_Y, 0);
    }

    //初始化边界为1
    public void initBound(int n) {
        for (int i = 0; i < n; ++i) {
            migong[i][0] = 1;
            migong[0][i] = 1;
            migong[n - 1][n - i - 1] = 1;
            migong[n - i - 1][n - 1] = 1;
        }
    }

    public void randomInit() {
        Random rd = new Random();
        int x, y;
        // 随机生成迷宫大小
        n = rd.nextInt(5) + 6;
        System.out.println("Size:"+n+"*"+n);
        migong = new int[n][n];
        initBound(n);
        // 随机生成起点或终点。
        start_X = rd.nextInt(n - 2) + 1;
        start_Y = rd.nextInt(n - 2) + 1;
        while(true) {
            end_X = rd.nextInt(n - 2) + 1;
            end_Y = rd.nextInt(n - 2) + 1;
            if(start_X!=end_X||start_Y!=end_Y){
                break;
            }
        }
        // 随机生成障碍物
        int times = rd.nextInt(((n - 2) * (n - 2) - 3)/2)+((n - 2) * (n - 2) - 3)/6;

        for (int i = 0; i < times; ++i) {
            x = rd.nextInt(n - 3) + 1;
            y = rd.nextInt(n - 3) + 1;
            // 如果随机生成到七点或终点，则跳过生成
            if ((x == start_X && y == start_Y) || (x == end_X && y == end_Y)) {
                continue;
            }
            migong[y][x] = 1;
            // 如果起点或终点四周都为1，则撤销此次随机障碍物
            if (((migong[start_Y - 1][start_X] == 1) &&
                    (migong[start_Y + 1][start_X] == 1) &&
                    (migong[start_Y][start_X + 1] == 1) &&
                    (migong[start_Y][start_X - 1] == 1))
                    ||
                    ((migong[end_Y - 1][end_X] == 1) &&
                            (migong[end_Y + 1][end_X] == 1) &&
                            (migong[end_Y][end_X + 1] == 1) &&
                            (migong[end_Y][end_X - 1] == 1))
            ) {
                migong[y][x] = 0;
            }
        }

    }

    public void printMiGong() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; j++) {
                if (j == start_X && i == start_Y) {
                    System.out.print("s");
                } else if (j == end_X && i == end_Y) {
                    System.out.print("e");
                } else if (migong[i][j] == 7) {
                    System.out.print("↑");
                } else if (migong[i][j] == 8) {
                    System.out.print("↓");
                } else if (migong[i][j] == 9) {
                    System.out.print("←");
                } else if (migong[i][j] == 10) {
                    System.out.print("→");
                } else if (migong[i][j] == 3) {
                    System.out.print(0);
                } else {
                    System.out.print(migong[i][j]);
                }
                System.out.print(" ");

            }
            System.out.print("\n");
        }
    }

    public boolean tryUp(int x, int y) {
        if (findWay(migong, x , y-1, 1)) {
            return true;
        }
        else {
            return false;
        }
    }

    public boolean tryDown(int x, int y) {
        if (findWay(migong, x , y+1, 2)) {
            return true;
        } else {
            return false;
        }
    }



    public boolean tryLeft(int x, int y) {
        if (findWay(migong, x-1, y , 3)) {
            return true;
        } else {
            return false;
        }
    }

    public boolean tryRight(int x, int y) {
        if (findWay(migong, x+1, y , 4)) {
            return true;
        } else {
            return false;
        }
    }

    public boolean[] judgeDirection(int now_x, int now_Y) {
        // 0~3表示终点在上下左右
        boolean direction[] = {false, false, false, false};
        if (now_x < end_X) {
            direction[3] = true;
        }
        if (now_x > end_X) {
            direction[2] = true;
        }
        if (now_Y < end_Y) {
            direction[1] = true;
        }
        if (now_Y > end_Y) {
            direction[0] = true;
        }
        System.out.print("end x,y="+end_X+","+end_Y+"now x,y="+now_x+","+now_Y+"  ");
        for (int index = 0; index < direction.length; ++index) {
            System.out.print(direction[index] + "  ");
        }
        System.out.print("\n");
        return direction;
    }

    public boolean findWay(int[][] migong, int x, int y, int orientation) {
        if (migong[end_Y][end_X] == 2 || migong[end_Y][end_X] == 7 || migong[end_Y][end_X] == 8 || migong[end_Y][end_X] == 9 || migong[end_Y][end_X] == 10 ||( (x==end_X)&&(y==end_Y))) {
            System.out.println("Result:");
            printMiGong();
            return true;
        } else {
            if (migong[y][x] == 0) {
                if (orientation == 1) {
                    migong[y][x] = 7;
                } else if (orientation == 2) {
                    migong[y][x] = 8;
                } else if (orientation == 3) {
                    migong[y][x] = 9;
                } else if (orientation == 4) {
                    migong[y][x] = 10;
                } else {
                    migong[y][x] = 2;
                }

                boolean direction[] = judgeDirection(x, y);
//                System.out.print("end x,y="+end_X+","+end_Y+"now x,y="+x+","+y+"  ");
//                for (int index = 0; index < direction.length; ++index) {
//                    System.out.print(direction[index] + "  ");
//                }
//                System.out.print("\n");

                if (direction[0]) {

                    if(tryUp(x,y)){
                        return true;
                    }
                    if(tryLeft(x,y)){
                        return true;
                    }
                    if(tryRight(x,y)){
                        return true;
                    }
                    if(tryDown(x,y)){
                        return true;
                    }
                }
                if (direction[1]) {
                    if(tryDown(x,y)){
                        return true;
                    }
                    if(tryLeft(x,y)){
                        return true;
                    }
                    if(tryRight(x,y)){
                        return true;
                    }
                    if(tryUp(x,y)){
                        return true;
                    }
                }
                if (direction[2]) {
                    if(tryLeft(x,y)){
                        return true;
                    }
                    if(tryDown(x,y)){
                        return true;
                    }
                    if(tryUp(x,y)){
                        return true;
                    }
                    if(tryRight(x,y)){
                        return true;
                    }
                }
                if (direction[3]) {
                    if(tryRight(x,y)){
                        return true;
                    }
                    if(tryDown(x,y)){
                        return true;
                    }
                    if(tryUp(x,y)){
                        return true;
                    }
                    if(tryLeft(x,y)){
                        return true;
                    }
                }

                    migong[y][x] = 3;
                    return false;

            }
            return false;
        }
    }
}