【Java基础】迷宫问题的Java代码实现

迷宫问题通常是指在给定的迷宫中,找到从起点到终点的路径的问题。迷宫通常由障碍物和自由空间组成,其中障碍物是不可穿越的区域,自由空间可以穿越。解决迷宫问题的方法有很多种,本文使用递归算法来解决迷宫问题。


一、使用递归算法来解决迷宫问题

使用递归算法来解决迷宫问题的思路是基于深度优先搜索(DFS)的,每次在当前位置尝试向上、向下、向左、向右四个方向进行探索,如果能够到达终点,则返回true,否则继续递归搜索。为了避免重复走过已经访问过的格子,我们需要使用一个二维数组记录每个格子是否被访问过。具体思路如下:

1、确定递归函数的参数和返回值:

  • 参数:当前位置的坐标 (x, y)、目标位置的坐标 (tx, ty)、迷宫矩阵 maze。
  • 返回值:如果能够从当前位置到达目标位置,则返回 true;否则返回 false。

2、在递归函数中,先判断当前位置是否越界或者是障碍物,若是则直接返回 false。

3、然后判断当前位置是否为目标位置,若是则返回 true。

4、如果不是目标位置,就依次向当前位置的上下左右四个方向递归搜索。注意,在进入每个方向的递归之前,需要将当前位置标记为已经走过,以避免重复访问。

5、如果四个方向都没有找到通往目标位置的路径,则返回 false。

6、最后,需要将当前位置标记为未走过,并将结果返回给调用者。

二、具体的代码实现

package com.biyu.demo;

public class MazeSolver {

    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;
        }
        //设置挡板, 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);
        setWay2(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();
        }

    }

    /**
     * 使用递归回溯来给小球找路
     * 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) { // 通路已经找到ok
            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;
            }
        }
    }


    /**
     * 修改找路的策略,改成 上->右->下->左
     *
     * @param map
     * @param i
     * @param j
     * @return
     */
    public static boolean setWay2(int[][] map, int i, int j) {
        if (map[6][5] == 2) { // 通路已经找到ok
            return true;
        } else {
            if (map[i][j] == 0) { //如果当前这个点还没有走过
                //按照策略 上->右->下->左
                map[i][j] = 2; // 假定该点是可以走通.
                if (setWay2(map, i - 1, j)) {//向上走
                    return true;
                } else if (setWay2(map, i, j + 1)) { //向右走
                    return true;
                } else if (setWay2(map, i + 1, j)) { //向下
                    return true;
                } else if (setWay2(map, i, j - 1)) { // 向左走
                    return true;
                } else {
                    //说明该点是走不通,是死路
                    map[i][j] = 3;
                    return false;
                }
            } else { // 如果map[i][j] != 0 , 可能是 1, 2, 3
                return false;
            }
        }
    }

}

  • 在实际应用中,可能需要对递归深度、搜索时间等进行限制,以避免无限递归导致程序异常或者性能问题。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/12415.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vLive带你走进虚拟直播世界

虚拟直播是什么&#xff1f; 虚拟直播是基于5G实时渲染技术&#xff0c;在绿幕环境下拍摄画面&#xff0c;通过实时抠像、渲染与合成&#xff0c;再推流到直播平台的一种直播技术。尽管这种技术早已被影视工业所采用&#xff0c;但在全民化进程中却是困难重重&#xff0c;面临…

【状态估计】基于增强数值稳定性的无迹卡尔曼滤波多机电力系统动态状态估计(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

TeeChart Pro ActiveX 2023.3.20 Crack

TeeChart Pro ActiveX 图表组件库提供数百种 2D 和 3D 图形样式、56 种数学和统计函数供您选择&#xff0c;以及无限数量的轴和 14 个工具箱组件。图表控件可以有效地用于创建多任务仪表板。 插件的多功能性 ActiveX 图表控件作为服务器端库中的 Web 图表、脚本化 ASP 图表或桌…

Docker应用部署

文章目录 Docker 应用部署一、部署MySQL二、部署Tomcat三、部署Nginx四、部署Redis Docker 应用部署 一、部署MySQL 搜索mysql镜像 docker search mysql拉取mysql镜像 docker pull mysql:5.6创建容器&#xff0c;设置端口映射、目录映射 # 在/root目录下创建mysql目录用于…

缩短客户响应时间的 5 种方法

在当今竞争激烈的世界中&#xff0c;客户服务就是确保卓越的客户体验。这意味着顶级品牌必须竞争为客户提供最好的客户服务&#xff0c;而且提供最快的响应时间。 改善客户服务响应时间的 5种方法 1.使用正确的客户服务软件 客户服务软件是您可以为提高客户服务而进行的最佳…

【JVM】常量池

常量池&#xff08;Runtime Constant Poo&#xff09; 常量池Java中可以分为三种&#xff1a;字符串常量池&#xff08;堆&#xff09;、Class文件常量池、运行时常量池&#xff08;堆&#xff09;。 1.字符串常量池&#xff08;String Pool&#xff09; 为了提升性能和减少…

C++ 23 实用工具(二)绑定工具

C 23 实用工具&#xff08;二&#xff09;绑定工具 Adaptors for Functions std::bind、std::bind_front、std::bind_back和std::function这四个函数非常适合一起使用。 其中&#xff0c;std::bind、std::bind_front和std::bind_back可以让您即时创建新的函数对象&#xff0c…

protobuf编码格式解析

示例 假如定义一个如下的protobuf类型 message Person {required string user_name 1;optional int64 favorite_number 2;repeated string interests 3; }将其赋值为: user_name : "Martin" favorite_number : 1337 interests:"daydrea…

(PCB系列三)AD六层板布线经验累积

目录 1、布局&#xff1a; 2、创建电源类PWR 3、高速部分可以加屏蔽罩&#xff0c; 4、EMMC和NANDFLASH采取兼容放置&#xff08;创建联合&#xff09; 5、HDMI设计 6、就近原则摆放 7、AV端口 8、模拟信号&#xff08;1字型或L型走线&#xff09; 9、WIFI模块 10、局…

【精华】表格结构识别模型研究进展

表格结构识别模型研究进展 合合信息&#xff1a;表格识别与内容提炼技术理解及研发趋势 OCR之表格结构识别综述 表格识别技术综述 用于表检测和结构识别的深度学习&#xff1a;综述 &#xff08;1&#xff09;PP-Structure 速度提升11倍&#xff0c;一键PDF转Word PP-St…

【软考备战·希赛网每日一练】2023年4月12日

文章目录 一、今日成绩二、错题总结第一题 三、知识查缺 题目及解析来源&#xff1a;2023年04月12日软件设计师每日一练 一、今日成绩 二、错题总结 第一题 解析&#xff1a; 依据题目画出PERT图如下&#xff1a; 关键路径长度&#xff08;从起点到终点的路径中最长的一条&…

递归算法_字符串反转_20230412

递归算法-字符串反转 前言 递归算法对解决重复的子问题非常有效&#xff0c;字符串反转也可以用递归算法加以解决&#xff0c;递归算法设计的关键是建立子问题和原问题之间的相关性&#xff0c;同时需要确立递归退出的条件&#xff1b;如果递归退出的条件无法确定&#xff0c…

说过的话就一定要办到 - redo日志

一、什么是redo日志&#xff1f; 如果我们只在内存的 Buffer Pool 中修改了页面&#xff0c;假设在事务提交后突然发生了某个故障&#xff0c;导致内存中的数据都失效了&#xff0c;那么这个已经提交了的事务对数据库中所做的更改也就跟着丢失了&#xff0c;这会导致事务会失去…

4.基于多目标粒子群算法冷热电联供综合能源系统运行优化

4.基于多目标粒子群算法冷热电联供综合能源系统运行优化《文章复现》 相关资源代码&#xff1a;基于多目标粒子群算法冷热电联供综合能源系统运行优化 基于多目标算法的冷热电联供型综合能源系统运行优化 考虑用户舒适度的冷热电多能互补综合能源系统优化调度 仿真平台:matl…

Segment Anything论文翻译,SAM模型,SAM论文,SAM论文翻译;一个用于图像分割的新任务、模型和数据集;SA-1B数据集

【论文翻译】- Segment Anything / Model / SAM论文 论文链接&#xff1a; https://arxiv.org/pdf/2304.02643.pdfhttps://ai.facebook.com/research/publications/segment-anything/ 代码连接&#xff1a;https://github.com/facebookresearch/segment-anything 论文翻译&…

性能测试,python 内存分析工具 -memray

Memray是一个由彭博社开发的、开源内存剖析器&#xff1b;开源一个多月&#xff0c;已经收获了超8.4k的star&#xff0c;是名副其实的明星项目。今天我们就给大家来推荐这款python内存分析神器。 Memray可以跟踪python代码、本机扩展模块和python解释器本身中内存分配&#xf…

VR全景展示,VR全景平台,助理全景展示新模式

引言&#xff1a; VR全景展示是一种新型的展示方式&#xff0c;它利用虚拟现实技术和全景拍摄技术&#xff0c;使参观者可以身临其境地进入虚拟展览空间。这种展示方式不仅能够提供更加沉浸式的参观体验&#xff0c;还可以解决传统展览所面临的时间和地域限制等问题。 VR全景展…

测试工具之JMH详解

文章目录 1 JMH1.1 引言1.2 简介1.3 DEMO演示1.3.1 测试项目构建1.3.2 编写性能测试1.3.3 执行测试1.3.4 报告结果 1.4 注解介绍1.4.1 BenchmarkMode1.4.2 Warmup1.4.3 Measurement1.4.4 Threads1.4.5 Fork1.4.6 OutputTimeUnit1.4.7 Benchmark1.4.8 Param1.4.9 Setup1.4.10 Te…

leetcode 812. 最大三角形面积

题目 给你一个由 X-Y 平面上的点组成的数组 points &#xff0c;其中 points[i] [xi, yi] 。从其中取任意三个不同的点组成三角形&#xff0c;返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案。 示例 1&#xff1a; 输入&#xff1a;points [[…

ActiveReportsJS 4.0 FIX ActiveReportsJS 4.0 Crack

JavaScript 报告工具是一组用于数据整合和可视化的 Web 组件。ActiveReportsJS 是前端开发人员用来在 Web 应用程序中嵌入报告的解决方案。报表设计器和查看器组件、强大的数据可视化器和丰富的 API 等主要功能使 ActiveReportsJS 成为行业领导者。 JavaScript 报告引擎 利用强…