package stack;
忘记上课了,正好好在寝室看到一个迷宫求解的问题,没想到真正实现还有点复杂,下面是实现源码,不过这并非最短路径解法
转载请注明出处,谢谢合作!
public class Maze {
static int[][] dedale={ //用二维数组表示地图
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,1,0,1,0},
{0,1,1,0,1,1,1,0,1,0},
{0,1,1,1,1,0,0,1,1,0},
{0,1,0,0,0,1,1,1,1,0},
{0,1,1,1,0,1,1,0,1,0},
{0,1,0,1,1,1,0,1,1,0},
{0,1,0,0,0,0,0,1,0,0},
{0,0,1,1,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0}};
public static void main(String[] args) {
Stack<Position> stack=new Stack<Position>();
Position start=new Position(1, 1);
Position current=start; //设置当前位置为起始位置
do{
if(dedale[current.x][current.y]==1&&validate(current)){ //当前位置可通(注:当前位置是标记过的位置时,路线肯定不对)
dedale[current.x][current.y]=9; //已经过的地方做个标记
stack.push(current);
if(current.x==8&¤t.y==8) break; //到达终点
current=nextPosition(current); //将当前指向下一个位置
}else{
if(stack.size()!=0){
current=stack.peek(); //取出当前栈顶元素
if(current.di>=4){ //此时此位置四个方向的路均不通时
dedale[current.x][current.y]=4; //留下不能通过的标记
stack.pop(); //pop出栈顶元素
current=stack.peek(); //获取此时栈顶元素
continue;
}
if(current.di<4) current=nextPosition(current);
}
} //end else
}while(stack.size()>0);
printPath(dedale);
}
public static void printPath(int[][] a){
for(int i=0;i<a.length;i++){
for(int j=0;j<a[i].length;j++)
System.out.print(a[i][j]+",");
System.out.println();
}
}
public static Position nextPosition(Position p){ //获取下一个Position
if(p.di==1){ //东
p.di++;
Position pos=new Position(p.x,p.y+1);
if(!validate(pos)) return nextPosition(p);
return pos;
}else if(p.di==2){ //南
p.di++;
Position pos=new Position(p.x+1,p.y);
if(!validate(pos)) return nextPosition(p);
return pos;
}else if(p.di==3){ //西
p.di++;
Position pos=new Position(p.x,p.y-1);
if(!validate(pos)) return nextPosition(p);
return pos;
}else if(p.di==4){ //北
p.di++;
Position pos=new Position(p.x-1,p.y);
return pos;
}else return null;
}
public static boolean validate(Position p){
if(dedale[p.x][p.y]==9||dedale[p.x][p.y]==4){ //排除已走过的部分
return false;
}
return true;
}
}
class Position{ //表示点实体
int x;
int y;
int di=1; //方向(direct)
public Position(){}
public Position(int x,int y){
this.x=x;
this.y=y;
}
}
最终结果:
0,0,0,0,0,0,0,0,0,0,
0,9,9,0,4,4,4,0,1,0,
0,1,9,0,4,4,4,0,1,0,
0,9,9,4,4,0,0,1,1,0,
0,9,0,0,0,1,9,9,9,0,
0,9,9,9,0,9,9,0,9,0,
0,1,0,9,9,9,0,9,9,0,
0,1,0,0,0,0,0,9,0,0,
0,0,1,1,1,1,1,9,9,0,
0,0,0,0,0,0,0,0,0,0,
分享到:
相关推荐
在本主题“数据结构-栈的应用-迷宫求解”中,我们将探讨如何利用栈来解决迷宫路径搜索的问题。 首先,迷宫求解是一个典型的图遍历问题,可以通过深度优先搜索(DFS)或广度优先搜索(BFS)等算法来解决。在这里,...
对于“图形化显示堆栈变化”,这意味着程序不仅执行迷宫求解,还会动态展示每一步决策如何影响堆栈的状态。这可以通过创建一个可视化界面来实现,比如使用Python的tkinter库或者JavaScript的HTML5 Canvas。每当你向...
非递归算法通常具有更好的性能,特别是在迷宫较大时,避免了递归可能导致的堆栈溢出问题。 在提供的压缩文件“迷宫问题”中,很可能包含了实现这两种算法的源代码。这些代码通常会包含以下部分: 1. **数据结构...
在Java中,非递归通常使用循环(如`for`循环)来实现。 示例代码: ```java public static int doFactorial(int n) { int result = 1; if (n ) { return -1; } if (n == 0) { return 1; } for (int i = 1; ...
- **栈**:在迷宫求解过程中,栈用于实现深度优先搜索(DFS)算法,记录回溯路径。 - **队列**:广度优先搜索(BFS)算法通常用队列存储待访问的节点,确保按顺序探索所有可能的路径。 2. **算法**: - **深度...
此外,还探索了栈和队列的应用,如进制转换、括号匹配检测和迷宫求解。 递归章节探讨了递归的概念、递归的实现与堆栈的关系,基于归纳的递归方法,以及递推关系的求解,并介绍了分治法的基本思想及其应用示例。 树...
代码03:使用迷宫求解器队列和堆栈搜索迷宫,提供了10个迷宫文件,从maze1.txt到maze10.txt。 代码04:散列字符串,使用多项式将字符串转换为整数,english_word文件包含30万个单词。 代码05:BinaryTree,二进制...
第四章聚焦于栈与队列的数据结构,讨论了它们的定义、抽象数据类型、存储实现以及应用示例,比如进制转换、括号匹配检测和迷宫求解。 第五章探讨了递归的概念以及递归与堆栈的关系,并介绍了基于归纳的递归和递推...
这个“二叉树迷宫”文件可能包含相关的Python、Java或C++代码示例,以及详细的步骤解释,帮助我们更好地理解和实现二叉树迷宫的构造与求解过程。如果你对数据结构和算法有兴趣,深入研究这个主题将有助于提升你的...
- **迷宫求解**:介绍使用栈解决迷宫问题的方法。 #### 第五章:递归 - **递归与堆栈** - **递归的概念**:介绍递归的基本定义及其特点。 - **递归的实现与堆栈**:讨论递归调用时与堆栈的关系。 - **基于归纳...
最后,书中讨论了堆栈在实现递归时的作用以及递归的几种常用算法,包括迷宫求解、括号匹配检测等。这些算法是理解算法设计策略的基础。 总体来说,《数据结构与算法 java版》为Java程序员提供了一本全面而深入的...
栈与队列都是基于线性表的结构,它们有特定的抽象数据类型和应用,比如括号匹配检测和迷宫求解。 递归是算法设计中的一个重要概念。在递归章节中,会介绍递归的概念、实现方式以及和堆栈的关系。此外,也会讨论基于...
- **迷宫求解**:介绍如何使用栈解决迷宫问题。 #### 递归 - **递归与堆栈** - **递归的概念**:解释递归的基本定义、特点以及递归的基本原理。 - **递归的实现与堆栈**:讨论递归实现中的堆栈使用及其作用。 ...
- **4.3.3 迷宫求解**:介绍如何使用栈解决迷宫问题。 #### 五、递归 第五章探讨了递归的基本原理和实现。 - **5.1 递归与堆栈** - **5.1.1 递归的概念**:解释递归的基本概念。 - **5.1.2 递归的实现与堆栈**...
包括栈和队列的顺序存储和链式存储实现,以及它们在进制转换、括号匹配检测和迷宫求解中的应用。本章通过实际的例子展示了这些基本数据结构的强大应用。 第五章“递归”着重讲述了递归的概念、与堆栈的关系,以及...