java寻找迷宫路径的简单实现示例
迷宫项目实现设计文档
项目介绍:
一个网格迷宫由n行m列的单元格组成,每个大院个要么是空地(用0表示),要么是障碍物(用1表示)。你的任务是找一条从起点到终点的移动序列,其中只能上下左右移动到相邻单元格。任何时候都不能在有障碍物的单元格中,也不能走到迷宫之外。起点为左上角和终点右下角。
项目功能:
解决迷宫路径查找问题,寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径,0代表可走,1代表不能行走,找到请输出最终的迷宫和路径信息,找不到请输出不存在有效路径。
项目所用知识点:
采用Java面向对象思想,二维数组以及非递归栈进行实现
项目实现思路:
1.定义一个迷宫节点类型(MazeNode)的二维数组
2.初始化每个格子中的value值。给二维数组每个格子存放对象。对象的value值只能为0(当前格子可以走)或者1(当前格子不能走)
3.创建围墙,可以有效防止越界问题。根据当前节点周围四个方向格子中的value值,判断当前节点的上下左右四个方向是否可走(0是可走,1不可走)。
4.开始走迷宫。采用栈操作,记录行走的路径,将元素入栈,判断当前栈顶元素的哪个方向可走,将其中一个可走方向进行入栈操作,直到右下角元素停止。栈中保存走过的路径。注意:如果遇到走入死胡同问题,此时需要将是栈顶元素并且栈顶元素的四个方向都不能行走,此时将其出栈,选择新方向再次入栈,直到右下角元素停止。
项目实现:
Maze类
importjava.util.Scanner; publicclassMaze{ privateMazeNode[][]mazenode; privateintrow;//行 privateintcolum;//列 publicMaze(){ } publicvoidinnode(){//添加迷宫路径; Scannerscanner=newScanner(System.in); System.out.println("请输入迷宫行数和列数"); row=scanner.nextInt()+2;//为后面加围墙 colum=scanner.nextInt()+2; System.out.println("请输入迷宫路径:"); mazenode=newMazeNode[row][colum]; build(mazenode);//创建一个row行colum列的mazenode并且把value值都给1 for(inti=1;imazenode类
publicclassMazeNode{ publicintindex1; publicintindex2; publicintvalue; publicMazeNode(intvalue,intindex1,intindex2){ this.value=value; this.index1=index1;//下标1 this.index2=index2;//下标2 } //改变找个点的值为2 publicvoidchangeValue(MazeNode[][]mazeNode,intindex1,intindex2){ mazeNode[index1][index2].value=2; } //判断左边是否可走 publicbooleanleft(MazeNode[][]mazeNode,intindex1,intindex2){ if(mazeNode[index1][index2].value==0){ returntrue; }returnfalse; } //判断上边是否可走 publicbooleanup(MazeNode[][]mazeNode,intindex1,intindex2){ if(mazeNode[index1][index2].value==0){ returntrue; }returnfalse; } //判断右边是否可走 publicbooleanright(MazeNode[][]mazeNode,intindex1,intindex2){ if(mazeNode[index1][index2].value==0){ returntrue; }returnfalse; } //判断下边是否可走 publicbooleandown(MazeNode[][]mazeNode,intindex1,intindex2){ if(mazeNode[index1][index2].value==0){ returntrue; }returnfalse; } }MyStake类//栈
importjava.util.Arrays; importjava.util.EmptyStackException; publicclassMyStack{ privatePuzzleValue[]array2; privateMazeNode[]array; privateintsize; privatefinalintINITSIZE=10; publicMyStack(){ array=newMazeNode[INITSIZE]; array2=newPuzzleValue[INITSIZE]; } //查找栈内是否存在此路径 publicbooleancontain(MyStackstack,MazeNode[][]mazeNode,intindex1,intindex2){ for(inti=0;i>1)); }else{ array[size]=mazeNode; size++; } } //出栈 publicvoidpop(MazeNodemazeNode){ if(size==0){ return; }else{ array[size]=null; size--; } } //获得栈顶元素 publicMazeNodegettop(){ returnarray[size-1]; } //改变栈内的value值 publicvoidtoRoute(){ for(inti=0;i 到此这篇关于java寻找迷宫路径的简单实现示例的文章就介绍到这了,更多相关java寻找迷宫路径内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票!