迷宫问题

整体问题

判断从起点能否走到终点，如果可以打印出来路径

思路

1.创建迷宫
2.设置起点和终点
3.如果走到终点退出递归
4.如果这个点没走过，假设它可以走通，递归的对它的四个方向走，如果通就返回true，四个方向都不通就返回false
5.如果这个点走过，就不能再走，直接返回false

优化策略

1.小球找到的路径与程序员设置的策略有关
2.可以将各种不同的策略共4乘3乘2乘1种策略依次走一遍，求最短

代码

package recursion;

public class Maze {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //创建数组
        //级别
        int [][] map=new int[8][7];
        //上下全部的置为1
        for(int i=0;i<7;i++) {
            map[0][i]=1;
            map[7][i]=1;
            
        }
        
        //左右都置为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.print(map[i][j]+" ");
            }
            System.out.println();
        }
        //使用递归回溯给小球找路
        boolean flag=setWay(map, 1, 1);
        System.out.println(flag);
        //输出新的地图，这个地图中就有小球走过的路
        //标识过的地图，有通路就是2，没有通路就是3
        for(int i=0;i<8;i++) {
            for(int j=0;j<7;j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        
    }
    
    //使用递归函数来给小球找路
    //map表示对应的矩阵
    //i,j表示从哪个位置开始找
    //表示如果找到通路的话，就返回true，否则就返回false
    //如果小球可以到map[6][5]位置，就说明通路已经找到，
    //约定，当地图的(i,j)为0的时候，表示没有走过，1表示墙，2是通路,3是之前走过但是没有走通
    //策略方法;下->右->上->左,如果走不通再结束
    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;
            }
        }
    
    }
    

}

迷宫问题

原文：https://www.cnblogs.com/mengxiaoleng/p/11644129.html