递归--迷宫问题（Java）

归子莫

发布于：2020年6月25日

递归–迷宫问题（Java）

博客说明

文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！

问题说明

制定好小球的移动路线，让它在迷宫里面找到终点的位置

问题思路

创建一个二维数组作为迷宫的地图
制定好小球的起点和终点位置
确定小球的运动规则，如下右上左
使用递归判断小球是否到达终点

代码

package question;

public class Migong {
    public static void main(String[] args) {
        //创建一个地图
        int[][] map = new int[8][7];
        //1表示墙，0表示可以移动，2代表已经走过，3代表失败
        //上下为墙
        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.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();
        }
    }

    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 {
                return false;
            }
        }
    }

}