迷宫问题求解

起始图形样例：?

代码思想：使用递归回溯算法，首先先选择一个方向进行，尝试着走，（行走的优先级 ： 下 右 上 左），如果走不通就将该路径设置为 3 。

实现代码如下：

public class Migong {
    public static void main(String[] args) {
        //初始化map地图
        int[][] map= new int[8][7];

        //将地图设置墙，值为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] =1;
        map[3][2] =1;

        //打印初始化的地图
        System.out.println("======起始地图======");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.printf("%d ",map[i][j]);
            }
            System.out.println();
        }

        //现在让小球走动，并且设置初始位置
        setWay(map,1 , 1);

        //重新打印最新的地图
        //打印初始化的地图
        System.out.println("======走过的地图======");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.printf("%d ",map[i][j]);
            }
            System.out.println();
        }

    }

    //编写递归方法
    public static Boolean setWay(int[][] map,int i, int j){
        //递归出口
        if(map[6][5] == 2){ //走到右下角的空格时，成功退出
            return true;
        }else {
            //尝试走动 采用 ==> 下 右 上 左
            if(map[i][j] == 0) {//如果空格没有走过
                map[i][j] = 2; //假设可以走的通
                if (setWay(map, i + 1, j)) { //向下走
                    return true;
                } else if (setWay(map, i, j + 1)) {
                    return true;
                } else if (setWay(map, i - 1, j)) {
                    return true;
                } else if (setWay(map, i, j - 1)) {
                    return true;
                } else {
                    map[i][j] = 3;
                    return false;
                }
            }
//            }else{//这里是可能是 1 ，2 ，3
//                return false; //这里也要给出出口，否则
//            }
        }
        return false;
    }
}

打印结果：

?特别说明：因为只有当map[6][5]唯一出口，因此其他情况都返回 false。所有，只要不是出口，返回false值就可以，在哪个地方不重要。