JAVA 解决迷宫问题

JAVA 解决迷宫问题

有一个迷宫，1是墙壁不可走，0是可以走的路.从入口出发，规定只能通过向上、向下、向左和向右方向进行走动，问如何才能找到一条到达出口的通路。

{1, 1, 1, 1, 1, 1, 1, 1, 1},
{0, 0, 1, 0, 0, 0, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1},
{1, 0, 0, 1, 0, 0, 1, 1, 1},
{1, 1, 0, 1, 1, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 0, 0, 1},
{1, 1, 0, 0, 0, 0, 1, 0, 0},
{1, 1, 1, 1, 1, 1, 1, 1, 1}

创建一个相同大小的二维布尔类型数组,如果走过改写为true

当每走过一个位置后，把改位置的值标记为-1，如果该位置标记为false，则不可以重复走

判断当前位置是否有路可走，根据向右、向下、向左、向上的顺序判断该位置的下一步是否有路可走

每走一步，需要把每一步的位置坐标保存起来，记录走过的位置

当走到死胡同，没路可走时，回溯到前面的位置，并判断该位置是否有路可走

如果有路可走，则继续往下走，反之则继续回退到前面一个位置继续查找，直到找到有路可走为止
 

代码实现:

public class Maze {
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},
            {0, 0, 1, 0, 0, 0, 1, 1, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 1, 1, 1},
            {1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 0, 0, 0, 0, 1, 0, 1},
            {1, 0, 1, 1, 1, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    //入口信息
    private static int entryX = 1;
    private static int entryY = 0;
    //出口信息
    private static int exitX = 7;
    private static int exitY = 8;
    //路径访问状态表
    private static boolean[][] vistied = new boolean[9][9];
    //方向的变化量
    private static int[][] direction = {
            {1, 0}, {0, 1}, {0, -1}, {-1, 0}
    };
    //存储路径的栈
    private static linkedList stack = new linkedList<>();

    public static void main(String[] args) {
        boolean flag = go(entryX, entryY);
        if (flag) {
            for (String path : stack) {
                System.out.println(path);
            }
        } else {
            System.out.println("迷宫不通！");
        }
    }

    //以x,y为入口 看是否能够向下找到出口 返回false找不到
    private static boolean go(int x, int y) {
        stack.push("(" + x + "," + y + ")");
        vistied[x][y] = true;
        if (x == exitX && y == exitY) {
            return true;
        }
        //考虑四个方向 上 右 下 左
        for (int i = 0; i < direction.length; i++) {
            int newX = direction[i][0] + x;
            int newY = direction[i][1] + y;
            if (isInArea(newX, newY) && isRoad(newX, newY) && !vistied[newX][newY]) {
                if (go(newX, newY)) {
                    return true;    //某一个方向能通 则向上返回true 表示此层次x y能通
                }
            }
        }
        stack.pop();
        return false;   //四个方向都不通 则向上返回false 表示此次层x y 不通
    }

    private static boolean isRoad(int x, int y) {
        return maze[x][y] == 0;
    }

    private static boolean isInArea(int x, int y) {
        return x >= 0 && x < 9 && y >= 0 && y < 9;
    }
}