分享是一种快乐,是一种美德,喜欢就分享吧。 网站首页 算法设计

递归算法实现迷宫解法

发布时间：2023-03-06 09:30:13编辑：admin阅读（170）

package com.atguigu.recursion;




public class MiGong {

    public static void main(String[] args) {

        int [][] map=new int[8][7];

        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;

//        map[1][2]=1;

//        map[2][2]=1;

        //输出地图

        for (int i = 0; i < 8; i++) {

            for (int j = 0; j <7 ; j++) {

                System.out.print(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.print(map[i][j]+" ");

            }

            System.out.println();

        }

    }

    //使用地柜回溯来给小孩找路

    /**

     * i,j表示从哪个位置开始找(1,1)

     * j 如果找到通路，就返回true，否则返回false

     * */

    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{

                //map[i][j]可能的取值是1、2、3

                return false;

            }




        }

    }

}