分布式服务 server ssis null openssl UIkit Parsley vue的钩子函数 vue循环数组 后台模板下载 后台管理界面模板 十大erp系统 建站一条龙 网赚教程下载 ps视频教程全集完整版 jq遍历对象 teamviewer验证被拒绝 js空格符 js回调函数写法 mysql数据库驱动 matlab求向量的模 python的range python文件 python学习文档 python文件读取 python数字类型 java课程学习 javasocket javastringbuilder java线程死锁 java接口实例 java多线程编程 java集合类型 网页游戏代码 sql语句大全实例教程 莫愁脚本 电脑必备软件排行榜 unix系统下载 快点蛆虫成就单刷 linux端口映射
当前位置: 首页 > 学习教程  > 编程语言

数据结构+算法--迷宫回溯问题分析和实现

2021/1/28 23:20:04 文章标签:

迷宫回溯问题思路代码实现思路 上图中代码的执行策略是:下->右->上->左 代码实现 public class MiGong {public static void main(String[] args) {//先创建一个二维数组 模拟迷宫//地图int[][] map new int[8][7];//使用1表示墙//上下全部置为1for(int…

迷宫回溯问题

  • 思路
  • 代码实现

思路

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
上图中代码的执行策略是:下->右->上->左

代码实现

public class MiGong {
    public static void main(String[] args) {

        //先创建一个二维数组 模拟迷宫
        //地图
        int[][] map = new int[8][7];
        //使用1表示墙
        //上下全部置为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;

        //输出地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.printf("%d \t",map[i][j]);
            }
            System.out.println();
        }

        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 \t",map[i][j]);
            }
            System.out.println();
        }
    }


    //使用 递归回溯 来给小球找路
    //说明:
    //1. map表示地图
    //2. i,j 表示从地图的哪个位置开始出发(1,1)
    //3. 如果小球能到 map[6][5] 位置,则说明通路找到
    //4. 约定:当map[i][j] 为0表示该点没有走过,当为1表示墙,2表示通路 可以走,3表示该点已经走过,但是走不通
    //5. 在走迷宫时,需要确定一个策略(方法) 下->右->上->左,如果该点走不通,再回溯
    /**
     *
     * @param map 表示地图
     * @param i   表示从哪个位置开始找
     * @param j
     * @return    如果找到通路,就返回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] != 0,可能是 1,2,3
                    return false;
            }
        }
    }
}


结果截图:
在这里插入图片描述
温馨提示:代码中 “设置挡板” 代码片段 改为
在这里插入图片描述
回溯效果更明显哦
在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_650175.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?