java寻找迷宫路径的简单实现示例
迷宫项目实现设计文档
项目介绍:
一个网格迷宫由n行m列的单元格组成,每个大院个要么是空地(用0表示),要么是障碍物(用1表示)。你的任务是找一条从起点到终点的移动序列,其中只能上下左右移动到相邻单元格。任何时候都不能在有障碍物的单元格中,也不能走到迷宫之外。起点为左上角和终点右下角。
项目功能:
解决迷宫路径查找问题,寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径,0代表可走,1代表不能行走,找到请输出最终的迷宫和路径信息,找不到请输出不存在有效路径。
项目所用知识点:
采用Java面向对象思想,二维数组以及非递归栈进行实现
项目实现思路:
1.定义一个迷宫节点类型(MazeNode)的二维数组
2.初始化每个格子中的value值。给二维数组每个格子存放对象。对象的value值只能为0(当前格子可以走)或者1(当前格子不能走)
3.创建围墙,可以有效防止越界问题。根据当前节点周围四个方向格子中的value值,判断当前节点的上下左右四个方向是否可走(0是可走,1不可走)。
4.开始走迷宫。采用栈操作,记录行走的路径,将元素入栈,判断当前栈顶元素的哪个方向可走,将其中一个可走方向进行入栈操作,直到右下角元素停止。栈中保存走过的路径。 注意: 如果遇到走入死胡同问题,此时需要将是栈顶元素并且栈顶元素的四个方向都不能行走,此时将其出栈,选择新方向再次入栈,直到右下角元素停止。
项目实现 :
Maze类
import java.util.Scanner; public class Maze { private MazeNode[][] mazenode; private int row ;//行 private int colum;//列 public Maze(){ } public void innode(){//添加迷宫路径; Scanner scanner=new Scanner(System.in); System.out.println("请输入迷宫行数和列数"); row=scanner.nextInt()+2;//为后面加围墙 colum=scanner.nextInt()+2; System.out.println("请输入迷宫路径:"); mazenode=new MazeNode[row][colum]; build(mazenode);//创建一个row行colum列的mazenode并且把value值都给1 for(int i=1;i<row-1;i++){//为围墙内value赋值; for(int j=1;j<colum-1;j++){ mazenode[i][j].value=scanner.nextInt(); } } } //创建围墙; public void build(MazeNode[][] mazenode){ for(int i=0;i<row;i++){ for(int j=0;j<colum;j++){ mazenode[i][j]=new MazeNode(1,i,j); } } } public void goMaze(){//走迷宫 innode(); MyStack route=new MyStack();//存放路径的盏 if(mazenode[1][1].value==0){//判断入口是否可走; route.push(mazenode[1][1]); }else {System.out.println("迷宫入口路径错误"); } if(mazenode[row-2][colum-2].value!=0){//判断终点是否正确 System.out.println("迷宫终点错误"); } for(int i=1,j=1;;){//起点 i=route.gettop().index1;//赋值栈顶元素的下标一给i j=route.gettop().index2;//赋值栈顶元素的下标二给j if(i==row-2&&j==colum-2){ break; }//抵达终点退出循环 if(mazenode[i][j].right(mazenode,i,j+1)){//判断右边是否可走 if(route.contain(route,mazenode,i,j+1)){//判断右边是否在栈内 mazenode[i][j].changeValue(mazenode,i,j); route.pop(mazenode[i][j]);//如果存在退栈 }else { route.push(mazenode[i][j+1]);//如果不存在入栈的右边 } } else if(i+1<row&&mazenode[i][j].down(mazenode,i+1,j)){ if(route.contain(route,mazenode,i+1,j)){//判断下边是否在栈内 mazenode[i][j].changeValue(mazenode,i,j); route.pop(mazenode[i+1][j]);退栈 }else { route.push(mazenode[i+1][j]); } }else if(i+1<row&&mazenode[i][j].left(mazenode,i,j-1)){ if(route.contain(route,mazenode,i,j-1)){//判断左边是否在栈内 mazenode[i][j].changeValue(mazenode,i,j); route.pop(mazenode[i][j]);退栈 }else{ route.push(mazenode[i][j-1]); } }else if(i+1<row&&mazenode[i][j].up(mazenode,i-1,j)){ if(route.contain(route,mazenode,i-1,j)){//判断上边是否在栈内 mazenode[i][j].changeValue(mazenode,i,j); route.pop(mazenode[i][j]);退栈 }else{ route.push(mazenode[i-1][j]); } } } route.toRoute();//修改路径的值 for(int i=1;i<row-1;i++){//进行打印 for(int j=1;j<colum-1;j++){ System.out.print(mazenode[i][j].value+" "); } System.out.println(); } } }
mazenode类
public class MazeNode { public int index1; public int index2; public int value; public MazeNode(int value,int index1,int index2) { this.value=value; this.index1=index1;//下标1 this.index2=index2;//下标2 } //改变找个点的值为2 public void changeValue(MazeNode[][] mazeNode,int index1,int index2){ mazeNode[index1][index2].value=2; } //判断左边是否可走 public boolean left(MazeNode[][] mazeNode,int index1,int index2){ if(mazeNode[index1][index2].value==0){ return true; }return false; } //判断上边是否可走 public boolean up(MazeNode[][] mazeNode,int index1,int index2){ if(mazeNode[index1][index2].value==0){ return true; }return false; } //判断右边是否可走 public boolean right(MazeNode[][] mazeNode,int index1,int index2){ if(mazeNode[index1][index2].value==0){ return true; }return false; } //判断下边是否可走 public boolean down(MazeNode[][] mazeNode,int index1,int index2){ if(mazeNode[index1][index2].value==0){ return true; }return false; } }
MyStake类//栈
import java.util.Arrays; import java.util.EmptyStackException; public class MyStack { private PuzzleValue[]array2; private MazeNode[]array; private int size; private final int INITSIZE=10; public MyStack(){ array=new MazeNode[INITSIZE]; array2=new PuzzleValue[INITSIZE]; } //查找栈内是否存在此路径 public boolean contain(MyStack stack,MazeNode[][] mazeNode,int index1,int index2){ for(int i=0;i<size;i++){ if(array[i].index1==index1&&array[i].index2==index2){ return true; } } return false; } //入栈 public void push(MazeNode mazeNode){ if(array.length==size){ array= Arrays.copyOf(array,array.length+(array.length>>1)); }else { array[size]=mazeNode; size++; } } //出栈 public void pop(MazeNode mazeNode){ if(size==0){ return; }else{ array[size]=null; size--; } } //获得栈顶元素 public MazeNode gettop(){ return array[size-1]; } //改变栈内的value值 public void toRoute(){ for(int i=0;i<size;i++){ array[i].value=3; } } }
到此这篇关于java寻找迷宫路径的简单实现示例的文章就介绍到这了,更多相关java 寻找迷宫路径内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
- 这篇文章主要介绍了Java连接数据库oracle中文乱码解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-05-16
- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19