程序员经验分享-hwhale

JavaSE-基于回溯法用类+栈实现迷宫问题

2023-05-16

目录

 

1.问题描述

2.自定义类栈

3.结点类

4.操作类

5.函数讲解

6.测试类及结果

1.问题描述

输入迷宫大小，以及路径，0表示可走路径，1表示死路，从输入矩阵的左上角起点到右下角终口（也可简单改动自定义起点和终点）找出一条能通过的路径。

如输入大小3*3，路径为

0  0  0

0  1  1

0  0  0

最终要做的是找到并将对应路径的值改写，比如说是2，用来表示找到的路径所在，如：

2  0  0

2  1  1

2  2  2

2.自定义类栈

思路：利用回溯法去做，每次进行结点探查，能走就走，路不通就返回，因此这里利用栈去做，自定义栈类如下：

栈中用一个自定义的MazeNode类型的一维数组存储结点信息，size为栈中有效元素个数，操作主要有入栈，出栈，取栈顶元素。

package com.maze;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 * Description :
 * Created by Resumebb
 * Date :2020/10/21
 */
public class MyStack {
    private MazeNode[] element;
    private int size;
    private static final int INITSIZE = 100;

    public MyStack(){
        element = new MazeNode[INITSIZE];
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    private void ensureCapacity(){
        if(size == element.length){
            element = Arrays.copyOf(element,element.length+(element.length>>1));
        }
    }

    public void push(MazeNode mazeNode,int row, int colum){
        ensureCapacity();
        element[size++] = mazeNode;
        mazeNode.setRow(row);
        mazeNode.setColum(colum);
    }

    public void pop(){
        if(size == 0){
            return;
        }
        size--;
    }

    public MazeNode peek(){
        if(size == 0){
            throw new EmptyStackException();
        }
        return element[size-1];
    }
}

3.结点类

接下来定义结点类：

成员变量有结点的方向，东南西北四个方向，当前所在行列坐标，以及当前结点的value值。

package com.maze;

/**
 * Description :
 * Created by Resumebb
 * Date :2020/10/21
 */
public class MazeNode {
    private int value;
    public boolean way_east;
    public boolean way_west;
    public boolean way_south;
    public boolean way_north;
    private int row;
    private int colum;

    public MazeNode(int value, int row, int colum){
        this.value = value;
        this.row = row;
        this.colum = colum;
    }

    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getColum() {
        return colum;
    }

    public void setColum(int colum) {
        this.colum = colum;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

4.操作类

定义操作类，寻路操作等在此类中进行：

package com.maze;

import java.util.Scanner;
import java.util.Stack;

/**
 * Description :
 * Created by Resumebb
 * Date :2020/10/21
 */
public class Maze {
    private MazeNode[][] mazeNodes;
    private int row;
    private int colum;

    public Maze(int row, int colum) {
        this.row = row;
        this.colum = colum;
        mazeNodes = new MazeNode[row][colum];
    }

    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getColum() {
        return colum;
    }

    public void setColum(int colum) {
        this.colum = colum;
    }

    public void goMaze(){
        initValue();
        if(mazeNodes[0][0].getValue() != 0){
            return;
        }
        initWayState();
        MyStack stack = run();
        display(stack);
    }

    public void initValue(){
        Scanner in = new Scanner(System.in);
        System.out.println("input route：");
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < colum; j++) {
                mazeNodes[i][j] = new MazeNode(in.nextInt(),i,j);
            }
        }
    }

    private void initWayState(){
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < colum; j++) {
                if(mazeNodes[i][j].getValue() == 0){
                    //东
                    if(j+1<colum && mazeNodes[i][j+1].getValue() == 0){
                        mazeNodes[i][j].way_east = true;
                    }

                    //西
                    if(j-1>=0 && mazeNodes[i][j-1].getValue() == 0){
                        mazeNodes[i][j].way_west = true;
                    }

                    //南
                    if(i+1<row && mazeNodes[i+1][j].getValue() == 0){
                        mazeNodes[i][j].way_south = true;
                    }

                    //北
                    if(i-1>=0 && mazeNodes[i-1][j].getValue() == 0){
                        mazeNodes[i][j].way_north = true;
                    }
                }
            }
        }
    }

    //0 0 0 0 1 1 0 0 0
    public MyStack run(){
        MyStack stack = new MyStack();
        int i = 0, j = 0;
        stack.push(mazeNodes[0][0]);

        while(stack.getSize()!=0){
            //东边可走
            if(j+1<colum && mazeNodes[i][j+1].getValue() == 0 && mazeNodes[i][j+1].way_west){
                stack.push(mazeNodes[i][j+1]);
                mazeNodes[i][j].way_east = false;
                mazeNodes[i][++j].way_west = false;
            }

            //南边可走
            else if(i+1<row && mazeNodes[i+1][j].getValue() == 0 && mazeNodes[i+1][j].way_north){
                stack.push(mazeNodes[i+1][j]);
                mazeNodes[i][j].way_south = false;
                mazeNodes[++i][j].way_north = false;
            }

            //西边可走
            else if(j-1>=0 && mazeNodes[i][j-1].getValue() == 0 && mazeNodes[i][j-1].way_east){
                stack.push(mazeNodes[i][j-1]);
                mazeNodes[i][j].way_west = false;
                mazeNodes[i][--j].way_east = false;
            }

            //北边可走
            else if(i-1>=0 && mazeNodes[i-1][j].getValue() == 0  && mazeNodes[i-1][j].way_south){
                stack.push(mazeNodes[i-1][j]);
                mazeNodes[i][j].way_north = false;
                mazeNodes[--i][j].way_south = false;
            }

            //四路不通出栈
            else {
                stack.pop();
                i = stack.peek().getRow();
                j = stack.peek().getColum();
            }

            if(i==row-1 && j==colum-1){
                return stack;
            }
        }
        return stack;
    }

    public void display(MyStack stack){
        int x = 0, y = 0;
        int len = stack.getSize();
        for (int i = 0; i < len; i++) {
            x = stack.peek().getRow();
            y = stack.peek().getColum();
            mazeNodes[x][y].setValue(2);
            stack.pop();
        }
        System.out.println("route:");
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < colum; j++) {
                System.out.print(mazeNodes[i][j].getValue()+" ");
            }
            System.out.println();
        }
    }
}

5.函数讲解

在该类中主要函数是initValue(); initWayState(); run(); display();

initValue函数：

该函数的作用主要用于存储路径的二维数组初始化的数据录入操作。

 

initWayState函数：

该函数的作用是用于对每个结点的方向进行初始化，如当前结点的右边是0，则将当前结点的way_east给置TRUE，如果下方也是0，则way_south给置TRUE，像这样将整个迷宫的所有结点的方向给初始化。

 

run函数：

该函数就是让孩子去闯去跳，去勇敢的倒挂金钩。

首先将起点给入栈，然后进行轮回，按照东南西北的顺时针方向去循环（因为我要靠近右下角的终点，这样搞快点），只要检测到四个方向哪个方向的下一个结点值为0，说明这条路是通的，并且它这个结点对应的反方向值为TRUE，举个例子：

0  0  0

0  1  1

0  0  0

if(j+1<colum && mazeNodes[i][j+1].getValue() == 0 && mazeNodes[i][j+1].way_west){
                stack.push(mazeNodes[i][j+1]);
                mazeNodes[i][j].way_east = false;
                mazeNodes[i][++j].way_west = false;
            }

我先把左上角第一个结点入栈，然后去遍历，该项右边结点的值为0，说明这是一条路径，然后看右边结点的西方向是否为TRUE（也可以判断当前结点的东方向是否为TRUE,但是我喜欢反着来），如果为TRUE，就相当于这条路径是能走的，那么就将当前结点入栈，然后把当前结点的东边方向和右边结点的西边方向给置FALSE，相当于过河拆桥，只能走一次，下次就不行了，桥已经炸了，判断的时候要注意边界问题。

当走到第3个结点时，发现右边没路，南边也是1，路不通，并且回去的路也给封了，此时就要将当前结点出栈，说明此路不通，开始浪子回头，并且将i，j指针指向出栈后新栈顶元素的行列坐标。

 stack.pop();
 i = stack.peek().getRow();
 j = stack.peek().getColum();

最后直到找到一条路径，将栈给返回。

 

display函数：

这个函数就是用来进行打印路径的，遍历栈中元素，获取行列坐标，将路径对应的结点值给换成2，进行打印输出。

  public void display(MyStack stack){
        int x = 0, y = 0;
        int len = stack.getSize();
        for (int i = 0; i < len; i++) {
            x = stack.peek().getRow();
            y = stack.peek().getColum();
            mazeNodes[x][y].setValue(2);
            stack.pop();
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < colum; j++) {
                System.out.print(mazeNodes[i][j].getValue()+" ");
            }
            System.out.println();
        }
    }

6.测试类及结果

最后一个测试类：

package com.maze;


import java.util.Scanner;

/**
 * Description :
 * Created by Resumebb
 * Date :2020/10/21
 */
public class TestDemo {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("input size:");
        int row = in.nextInt();
        int colum = in.nextInt();
        Maze maze = new Maze(row,colum);
        maze.goMaze();
    }
}

 

测试后结果：

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

JavaSE-基于回溯法用类+栈实现迷宫问题 的相关文章

  • MobileNet学习记录-概念篇

    MobileNet 1 网络简介 MobileNet模型是Google公司近年来提出的一种轻量级深度神经网络 xff0c 主要用于移动和嵌入式平台开发使用 MobileNets主要是从最初引入的深度可分离卷积构建的 xff0c 并随后用于I

  • Node将JS与Puppeteer打包成exe使用

    pkg pkg是一个可以将nodejs代码打包封装成可执行文件的工具 xff0c 安装命令如下 xff1a npm install g pkg 打包命令如 xff1a 默认会打包三个平台的可执行文件 xff0c win mac linux

  • Ubuntu 连接 wifi -亲测可用

    连接wifi 修改 etc network interfaces 文件 这个文件是定义网络配置的 sudo vim etc network interfaces interfaces 修改后文件内容如下 xff1a auto eth0 if

  • 卷积神经网络CNN学习记录-概念篇

    卷积神经网络CNN 1 网络简介 卷积神经网络 xff08 Convolutional Neural Network xff09 是人工神经网络与深度学习相结合 xff0c 它是一种具有卷积计算并且具有深度结构的前馈神经网络经 xff0c

  • 卷积神经网络CNN学习记录-实战篇（Minst手写数据集识别）

    from tensorflow examples tutorials mnist import input data import tensorflow as tf minst 61 input data read data sets 34

  • 卷积神经网络CNN学习记录-CNN实现语义分割（Encoder-Decoder结构）

    1 Encoder from keras layers import def Conv Encoder input height 61 416 input width 61 416 Img In 61 Input shape 61 inpu

  • MobileNet学习记录-基于MobileNetV1的自动驾驶图像语义分割实现

    1 MobileNet基础及架构 Mobielnet学习记录 概念篇 2 实现思路 为了便于实现 xff0c 还是采用了Encoder Decoder结构 xff0c 利用MobileNet来进行特征提取 xff0c 相较于CNN的卷积操作

  • STM32F407-SPI通信接口

    1 SPI概念 SPI xff0c 是一种高速的 xff0c 全双工 xff0c 同步的通信总线 xff0c 并且在芯片的管脚上只占用四根线 xff0c 节约了芯片的管脚 xff0c 同时为PCB的布局上节省空间 xff0c 提供方便 xf

  • Python学习-变量类型

    1 单变量赋值 等号 xff08 61 xff09 用来赋值 xff0c 左边是一个变量名 xff0c 右边是存储在变量中的值 xff0c 定义变量不需要声明类型 xff0c 可以直接赋值使用 例 xff1a temp1 61 100 赋值

  • Python学习-条件循环

    1 while循环 while循环的语句格式为 xff1a while condition statements 当判断条件为真时 xff0c 就会执行循环中的语句 xff0c 当条件为假时退出循环 xff0c 若条件为一个永真式 xff0

  • Python学习-函数模块

    1 函数定义 定义规则 xff1a 函数代码块以 def 关键词开头 xff0c 后接函数标识符名称和圆括号 任何传入参数和自变量必须放在圆括号中间 圆括号之间可以用于定义参数 函数的第一行语句可以选择性地使用文档字符串 用于存放函数说明

  • STM32F407控制42,57两个步进电机用传感器限制位置

    功夫不负有心人 xff0c 终于把这个做出来了 xff0c 本项目为控制42 57两个步进电机 xff0c 带动齿轮 xff0c 进行上下左右转动 xff0c 四个限位金属传感器限制位置 传感器配置过程 步进电机配置过程 记录一下一个问题

  • Python学习-多线程

    1 线程 首先区分线程和进程两个概念 xff1a 进程是资源 xff08 CPU 内存等 xff09 分配的基本单位 xff0c 它是程序执行时的一个实例 程序运行时系统就会创建一个进程 xff0c 并为它分配资源 xff0c 然后把该进程

  • Spring MVC controller出错后进入了不该进入的拦截器

    拦截器对一些接口进行了排除 xff0c 使这些接口不用进入拦截器的验证 xff0c 但是出现了一个现象 xff0c 例如 api v1 auth register 这个接口 xff0c 如果因为某些原因 xff0c 出现异常了 xff0c

  • Git学习-本地仓库与版本管理

    一 创建仓库 1 创建空仓库 在合适的位置创建一个新目录 xff0c Git Bash支持的是linux命令操作 第一种方法 xff1a mkdir mygit cd mygit pwd 用mkdir创建目录 xff0c pwd查看当前路径

  • STM32F407用wk2124芯片编写SPI转四路串口驱动

    目录 引言 一 SPI通信配置 1 GPIO初始化设置 2 SPI参数配置 3 读写函数 4 速度设置 二 WK2124逻辑代码编写 1 片选初始化 2 写寄存器函数 3 读寄存器函数 4 写FIFO函数 5 读FIFO函数 6 WK212

  • Git学习-远程仓库

    创建远程仓库 本地现在有一个仓库git xff0c 同时可以在github上创建一个同名的git仓库 xff0c 可以供自己和他人协同操作 1 在github电机new repository创建一个新仓库 xff0c 名称保持与本地一致 R

  • Python学习-SQLite

    SQLite是一种嵌入式数据库 xff0c 它的数据库就是一个文件 由于SQLite本身是C写的 xff0c 而且体积很小 xff0c 所以 xff0c 经常被集成到各种应用程序中 xff0c 甚至在iOS和Android的App中都可以集

  • Python学习-TCP网络编程

    1 客户端 Socket是网络编程的一个抽象概念 通常我们用一个Socket表示 打开了一个网络链接 xff0c 而打开一个Socket需要知道目标计算机的IP地址和端口号 xff0c 再指定协议类型即可 大多数连接都是可靠的TCP连接 创

  • Git学习-分支

    在Git里 xff0c 主分支为master分支 HEAD也不是指向提交 xff0c 而是指向master xff0c master才是指向提交的 xff0c 所以 xff0c HEAD指向的就是当前分支 一开始的时候 xff0c mast

随机推荐

  • Matplotlib绘制各类图像（折线图，曲线图...）-画图的神

    Matplotlib简介 Matplotlib是一个Python工具箱 xff0c 用于科学计算的数据可视化 借助它 xff0c Python可以绘制如Matlab和Octave多种多样的数据图形 最初是模仿了Matlab图形命令 但是与M

  • STM32F407多路串口通信进行数据收发

    一直被说是就不能把几个串口放在一起 xff0c 写个标准例程直接用 xff0c 非要每次用哪个串口才现场改程序 xff0c 被迫把usart1 usart2 usart3进行了资源整合 xff0c 挂在这以备不时之需 功能简述 xff1a

  • 基于Keras实现电影评论文本分类与RNN实现

    notebook使用评论文本将影评分为积极 xff08 positive xff09 或消极 xff08 nagetive xff09 两类 这是一个二元 xff08 binary xff09 或者二分类问题 xff0c 一种重要且应用广泛

  • 基于STM32F407的七要素气象站（气象传感器）CR-WS数据处理实现

    一 七要素气象站介绍 1 七要素气象站介绍 开发板还是采用STM32F407 485连线 xff1a 如果买了变送器就按照下图连线 xff1a 没有买变送器的话 xff0c 直接从气象站上拉线 xff0c 红正黑负 xff0c 黄485 A

  • MyBatis Plus 分页查询，total字段为0，分页未生效

    1 未配置 MybatisPlusInterceptor 64 Bean public MybatisPlusInterceptor mybatisPlusInterceptor MybatisPlusInterceptor interce

  • JavaSE学习记录-整数逆序+数组删除元素

    数组定义方法 int arr 61 new int 10 定义同时进行赋值 xff1a int arr 61 new int 1 2 3 4 5 数组打印方法 1 for循环打印 for int i 61 0 i lt arr length

  • FAFTS文件系统常用函数学习

    一 FATFS文件系统基础知识 1 简介 文件系统可以从官网进行下载 官网地址 xff1a http elm chan org fsw ff 00index e html FATFS是一个完全免费开源的FAT 文件系统模块 xff0c Fa

  • Leetcode-旋转数组+最后一个单词长度

    给定一个数组 xff0c 将数组中的元素向右移动 k 个位置 xff0c 其中 k 是非负数 示例 1 输入 1 2 3 4 5 6 7 和 k 61 3 输出 5 6 7 1 2 3 4 解释 向右旋转 1 步 7 1 2 3 4 5 6

  • Leetcode-最短路径和+最大子串和（动态规划）

    给定一个包含非负整数的 m x n 网格 xff0c 请找出一条从左上角到右下角的路径 xff0c 使得路径上的数字总和为最小 说明 xff1a 每次只能向下或者向右移动一步 示例 输入 1 3 1 1 5 1 4 2 1 输出 7 解释

  • LeetCode-二进制串和+宝石与石头

    给你两个二进制字符串 xff0c 返回它们的和 xff08 用二进制表示 xff09 输入为 非空 字符串且只包含数字 1 和 0 示例 1 输入 a 61 34 11 34 b 61 34 1 34 输出 34 100 34 示例 2 输

  • JavaSE数组练习-句子翻转+字符替换+打印特殊三角

    1 句子翻转 要求 xff1a 给定字符串如 34 hello i am a student 34 xff0c 对英语句子进行翻转 xff0c 并保持英语单词的顺序不变 xff0c 对标点符号当成字母处理 代码实现 xff1a import

  • 视觉SLAM学习--基础篇（SLAM框架及相机模型）

    一 例子 如上图的小萝卜机器人 xff0c 要使其具有自主运动能力至少需要两个条件 xff1a 1 我在什么地方 xff1f 定位 2 周围环境是什么样 xff1f 建图 因此它既需要知道自身的状态 位置 xff0c 也要了解所在的环境 地

  • Linux各类软件安装配置问题记录

    1 Ubuntu侧边栏和顶部栏消失不见 解决方法 xff1a 鼠标右键或者快捷键打开终端输入命令 dconf reset f org compiz 输入命令 setsid unity 一般到这一步侧边栏就会出现了 xff0c 如果没有出现就

  • 代码模拟确定有限自动机（DFA）执行过程

    一个确定有限自动机 xff08 DFA xff09 M是一个五元组 xff1a M 61 xff08 K xff0c xff0c f xff0c S xff0c Z xff09 其中 K是一个有穷集 xff0c 它的每个元素称为一个状态 x

  • 视觉SLAM-Eigen学习实践

    1 Eigen库介绍 Eigen 是一个 C 43 43 开源线性代数库 它提供了快速的有关矩阵的线性代数运算 xff0c 还包括解方程等功能 可以通过sudo apt install libeigen3 dev命令进行安装 xff0c 也

  • 苹果手机存储空间(或称为内存)满了导致黑屏转圈白苹果

    没刷机 xff0c 啥也没干 xff0c 发现把SIM卡拔了再开机就好了 xff0c 然后赶紧去卸载一些软件腾出空间

  • Arrays的toString方法和deepToString方法比较

    因为打印二维数组时用错了方法 xff0c 一般是用Arrays deppToString或者遍历使用toString xff0c 我直接用Arrays toString去打印了二维数组 xff0c 没有打印出正常二维数组的内容 xff0c

  • JavaSE-类与对象+单例模式

    1 类与对象的引用 概念 xff1a 如果一个变量的类型是类类型 xff0c 而非基本类型 xff0c 那么该变量又叫做引用 new testClass 该操作表示创建了一个testClass对象 xff0c 但没有办法访问这个对象 tes

  • JavaSE-类与对象-ATM自主操作系统实现

    学完类与对象的练习小作业 xff0c 主要有三个类 xff1a 银行卡类包含银行卡的相关信息如卡号 xff0c 密码 xff0c 姓名 xff0c 余额 xff1b 银行类中主要定义了一个银行卡数组 xff0c 用来存储当前用户的银行卡信息

  • JavaSE-基于回溯法用类+栈实现迷宫问题

    目录 1 问题描述 2 自定义类栈 3 结点类 4 操作类 5 函数讲解 6 测试类及结果 1 问题描述 输入迷宫大小 xff0c 以及路径 xff0c 0表示可走路径 xff0c 1表示死路 xff0c 从输入矩阵的左上角起点到右下角终口

热门标签