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,
分享到:
相关推荐
完整的,可以运行的代码。CPP文件在Xcode上实验通过。
用堆栈求解迷宫问题的演示。参考清华大学严蔚敏《数据结构》教材。
堆栈+数据结构 实现迷宫模拟算法
堆栈实现迷宫源代码。需要的请赶紧下载
使用“穷举求解”方法实现迷宫问题求解,以递归形式的算法求得迷宫中所有可能的通路,以方阵形式输出迷宫及其通路。
改算法值得自习体会 涉及到栈和队列的综合应用
C++实现的迷宫问题求解,使用的栈进行迷宫路径求解。。。。
利用平台SDK和数据结构实现迷宫求解,如果能把这些数据结构的算法使用在SDK上,那么就可以开发出 Windows 程序的算法程序提高学习,不用在 单调的console mode 中看着冷冰冰的字符来学习数据结构了,这样学习一方面可以...
寻找一个由 0 1 构成的迷宫的最优通路和所有通路。读入方式为文件读取,输入文件路径之后使用堆栈来求解迷宫的最优解和所有可能的解
java堆栈信息dump文件
用 Java 实现数据结构中的堆栈 用 Java 实现数据结构中的堆栈
数据结构中的堆栈有着广泛的应用,思维严密,仅供大家参考。
用队列和堆栈实现迷宫求解,动态分配迷宫大小,打印正确线路
这个一定让你满意的C语言版本的迷宫,用到堆栈
用堆栈解决迷宫问题 很好的哦 嘿嘿 让大家共享下
走迷宫
java堆栈详解
用堆栈储存迷宫,并寻找路径,运行结果以图示呈现,注释详细
打印JAVA堆栈的方法