Java 递归算法解迷宫问题

56 阅读 0 评论 37 点赞

我是靠谱客的博主自觉茉莉，最近开发中收集的这篇文章主要介绍Java 递归算法解迷宫问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这里写图片描述

上图是一个迷宫的图，0表示可以通过，1表示不可以通过，只能往上下左右走，左上角进去从右下角出去。
可以用一个二维数组来定义迷宫的初始状态，然后从左上角开始，不停的去试探所有可行的路线，碰到1就结束，然后继续探索其他的方向，为了防止在两个可行的格子之间来回走，我们需要标记一下已经走的路线。直到走到右下角出口为止，算找到了一个正确路径。
具体程序实现：

public class MyClass {

    private static int line = 4;

    private static int[][] array = new int[][] {
            {0,0,0,1},
            {0,0,0,1},
            {0,1,0,1},
            {0,0,0,0}
    };

    public static void main(String[] args) {
        move(0, 0);
    }


    private static void move(int i, int j) {
        if (i == line - 1 && j == line - 1) {
            print();
        }

        if (canMove(i, j, i, j+1)) {
            array[i][j] = 8;
            move(i, j + 1);
            array[i][j] = 0;
        }

        if (canMove(i, j, i + 1, j)) {
            array[i][j] = 8;
            move(i + 1, j);
            array[i][j] = 0;
        }

        if (canMove(i, j, i, j - 1)) {
            array[i][j] = 8;
            move(i, j - 1);
            array[i][j] = 0;
        }

        if (canMove(i, j, i - 1, j+1)) {
            array[i][j] = 8;
            move(i - 1, j);
            array[i][j] = 0;
        }
    }

    private static boolean canMove(int i, int j, int targetX, int targetY) {
        // 碰到左边
        if (i < 0 || j < 0) {
            return false;
        }
        // 碰到右边
        if (i >= line || j >= line) {
            return false;
        }

        // 不能走
        if (array[i][j] == 1 || array[i][j] == 8) {
            return false;
        }

        System.out.println("From(" + (i + 1) + "," + (j + 1) + ")"
                + "To(" + (targetX + 1) + "," + (targetY + 1) + ")" );
        return true;
    }

    private static void print() {
        System.out.println("得到一个解：");
        for (int i = 0; i < line; i++) {
            for (int j = 0; j < line; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
}