摘要：这周数据结构老师布置了一个作业，用栈来实现迷宫的求解，本来是要求自己写一个栈的类来实现，但是自己懒得写了，因为递归也是栈的一种实现，就直接用了递归来写。
这周数据结构老师布置了一个作业，用栈来实现迷宫的求解，本来是要求自己写一个栈的类来实现，但是自己懒得写了，因为递归也是栈的一种实现，就直接用了递归来写。
迷宫求解，主要用的是穷举法:从起始位置开始，向东南西北四个方向每个方向都尝试走，在每一个尝试中，若可通，则纳入当前路径，将下一位置切换为当前位置，再开始进行尝试，直到到达出口。若不可通，应回退到前一个通快，除去尝试过的方向再探索，四个方块都不可通，则删除当前的通道块,这个后进先出的操作，可以用栈来实现，当然也能用递归实现。
我想的是，迷宫应该有四个方法:
1.随机初始化迷宫(设置起点，终点，障碍)
2.迷宫求解(算出迷宫的解答方法)
3.展示迷宫
4.判断迷宫元素是否能够移动
public interface Maze {
ArrayList> init(ArrayList> maze, int size, int obstacleNumber);//初始化迷宫
void show();//展示迷宫
boolean getAnswer(E element);//获得迷宫的解
E move(int x, int y);//移动迷宫元素
}
在给迷宫初始化的时候遇到了问题，不能够设置相同的起点和终点，不能设置相同的障碍，不能给起点和终点设置障碍。对于起点和终点，判断一下就可以了，但是对于障碍一个个判断繁琐，想了一下只好用一个字符串表示元素的状态了。
初始化:
@Override
public ArrayList> init(ArrayList> maze, int size, int obstacleNumber) {
// TODO Auto-generated method stub
//初始化起点
int startX = (int) (Math.random() * size);
int startY = (int)(Math.random() * size);
E start = (E)maze.get(startY).get(startX);
start.setStatus("start");
this.start = start;
//初始化终点
int endlX = 0;
int endlY = 0;
E end = null;
do {
endlX = (int) (Math.random() * size);
endlY = (int) (Math.random() * size);
end = (E)maze.get(endlY).get(endlX);
} while(end.equals(start));
end.setStatus("endl");
this.end = end;
//初始化障碍
int number = 0;
while(number < obstacleNumber) {
int obstacleX = (int) (Math.random() * size);
int obstacleY = (int) (Math.random() * size);
E obstacle = maze.get(obstacleY).get(obstacleX);
if (!obstacle.equals(start) && !obstacle.equals(end)) {
if (obstacle.getStatus() != null) {
if (obstacle.getStatus().equals("obstacle")) {
continue;
}
} else {
number++;
obstacle.setStatus("obstacle");
}
}
}
this.maze = maze;
this.size = size;
return maze;
}
初始化结果是这样的:
虽然很丑，但是没什么办法，毕竟是控制台输出的。
接下来就是求迷宫的解了，因为每一个迷宫元素的求解步骤都一样，所以写了一个递归函数，主要就是向上下左右依次查看是否能“通路”，若能通，则跳到下一个元素在进行递归，若不通，则标记元素不可通，若到达迷宫尾或迷宫头，则结束。照着这个想法写，虽然中间出现了不够细心的错误，但最后还是能写出答案的。
迷宫求解:
@Override
public boolean getAnswer(E element) {
// TODO Auto-generated method stub
//若为最后一个结束
if (element.equals(end)) {return true;}
E next = element;
//向上移动
if ((next = this.move(element.getX(), element.getY() - 1)) != null && !next.equals(start) ) {
if (!next.equals(this.end)) {
next.setStatus("existen");
}
next.setRoute("向上");
if(this.getAnswer(next)) {return true;}
}
//向左移动
if ((next = this.move(element.getX() - 1, element.getY())) != null && !next.equals(start) ) {
next.setRoute("向左");
if (!next.equals(this.end)) {
next.setStatus("existen");
}
if(this.getAnswer(next)) {return true;}
}
//向下移动
if ((next = this.move(element.getX(), element.getY() + 1)) != null && !next.equals(start) ) {
next.setRoute("向下");
if (!next.equals(this.end)) {
next.setStatus("existen");
}
if(this.getAnswer(next)) {return true;}
}
//向右移动
if ((next = this.move(element.getX() + 1, element.getY())) != null && !next.equals(start)) {
next.setRoute("向右");
if (!next.equals(this.end)) {
next.setStatus("existen");
}
if(this.getAnswer(next)) {return true;}
}
if (!element.equals(start)) {
element.setStatus("noexisten");
element.setRoute(null);
}
return false;
}
最后:
还有的缺陷就是他不能找到最短的路径，想来这个实现没有头绪，老师也不要求，就没有尝试了。还有当没有答案时它也没有提示，懒得写了。
总结:这个作业还是挺有意思的，感觉是让自己对栈和递归有了个认识把。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/77246.html
