利用栈实现迷宫的求解
问题描述:这时实验心理学中的一个典型的问题,心理学家吧一只老鼠从一个无顶的大盒子的入口处赶进迷宫。迷宫设置很多隔壁,对前进方向形成了许多障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠仔迷宫中寻找通路以到达出口。
求解思想:回溯法是一种不断试探且及时纠正错误的搜索方法,下面的求解过程采用回溯法。从入口出发,按某一方向向前探索,若能走通(未走过 的),即某处可以到达,则到达一个新点,否则试探下一个方向;若所有的方向均没有通路,则沿原路返回前一点,换下一个方向继续试探,直到所有可能的通路都 搜索到,或找到一条通路,或无路可走又返回到入口点。这里可以用一个栈来实现,每走一步,将该位置压入栈中,若该点无路可走,则出栈返回上一位置。
需要解决的四个问题:
(1)表示迷宫的数据结构
设迷宫为m行n列,利用数组maze[m][n]来表示一个迷宫,maze[i][j]=0或1,其中0表示通路,1表示不通。迷宫该数组四边都为1,代表迷宫四周都是墙。这样就可以保证每个点都有8个方向可以试探。
入口为(1,1),出口为(6,8)
1,1,1,1,1,1,1,1,1,1 1,0,1,1,1,0,1,1,1,1 1,1,0,1,0,1,1,1,1,1 1,0,1,0,0,0,0,0,1,1 1,0,1,1,1,0,1,1,1,1 1,1,0,0,1,1,0,0,0,1 1,0,1,1,0,0,1,1,0,1 1,1,1,1,1,1,1,1,1,1
(2)试探方向
迷宫中间每个点都有8个方向可以试探。其增量数组可以用一个1*2的二维数组move表述,具体值如下:
x y 0 0 1 1 1 1 2 1 0 3 1 -1 4 0 -1 5 -1 -1 6 -1 0 7 -1 1
在move数组中,x表示横坐标的增量,y表示纵坐标的增量。
(3)栈中存放元素的设计
栈中所存放的元素应该包含所到达的每点的坐标以及从该点沿哪个方向向下走的。可以用一个类表示:
class Step{ int x,y,d; public Step(int x,int y,int d) { this.x = x;//横坐标 this.y = y;//纵坐标 this.d = d;//方向 }
(4)防止重复到达某点而发生死循环
可以用两种方法来实现,第一种就是另外设置一个标志数组mark[m][n],它的所有元素初始都为0,一旦到达某点,则设置该点的标志位1, 下次试探的时候就不再走这点了。第二种就是当到达某点的时候,使maze[i][j]置为-1,以便区别为达到的点,同样也可以防止走重复点的作用。
具体代码如下:
package com.stack; import java.util.Stack; * 用栈来实现迷宫的求解 * @author 刘玲 class Step{ int x,y,d; public Step(int x,int y,int d) { this.x = x;//横坐标 this.y = y;//纵坐标 this.d = d;//方向 public class MazeTest { public static void main(String[] args) { // 迷宫定义 int[][] maze = {{1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,1,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,0,1,1,0,0,0,1}, {1,0,1,1,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1,1,1}}; int[][] move = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; Stack Step s = new Stack Step Stack Integer s1 = new Stack Integer int a = path(maze, move, s); while(!s.isEmpty()){ Step step = s.pop(); System.out.println(step.x+":"+step.y); public static int path(int[][] maze,int[][] move,Stack Step s){ Step temp = new Step(1,1,-1); //起点 s.push(temp); while(!s.isEmpty()){ temp = s.pop(); int x = temp.x; int y = temp.y; int d = temp.d+1; while(d 8){ int i = x + move[d][0]; int j = y + move[d][1]; if(maze[i][j] == 0){ //该点可达 temp = new Step(i,j,d); //到达新点 s.push(temp); x = i; y = j; maze[x][y] = -1; //到达新点,标志已经到达 if(x == 6 y == 8){ return 1; //到达出口,迷宫有路,返回1 }else{ d = 0; //重新初始化方向 }else{ d++; //改变方向 return 0; }
输出结果如下:
6:8
5:8
5:7
5:6
4:5
3:5
3:4
3:3
2:2
由于栈是后进先出的,所以结果应该从下面看起(2,2)- (3,3)- (3,4)- (3,5)- (4,5)- (5,6)- (5,7)- (5,8)- (6,8)
有运行结果可以看出来,栈中所存储的就是迷宫的一条通路。
上面那个代码有一点点小问题,非常感谢问题的提出者,修改如下:
package com.stack; import java.util.Stack; * 用栈来实现迷宫的求解 * @author 刘玲 class Step{ int x,y,d; public Step(int x,int y,int d) { this.x = x;//横坐标 this.y = y;//纵坐标 this.d = d;//方向 public class MazeTest { public static void main(String[] args) { // 迷宫定义 int[][] maze = {{1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,1,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,0,1,1,0,0,0,1}, {1,0,1,1,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1,1,1}}; int[][] move = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; Stack Step s = new Stack Step int a = path(maze, move, s); while(!s.isEmpty()){ Step step = s.pop(); System.out.println(step.x+":"+step.y); public static int path(int[][] maze,int[][] move,Stack Step s){ Step temp = new Step(1,1,-1); //起点 s.push(temp); while(!s.isEmpty()){ //temp = s.pop(); 这样写是有问题的,不能将出栈的元素作为当前位置,应该将栈顶元素作为当前位置 s.pop(); //如果路走不通就出栈 if(!s.isEmpty()){ temp = s.peek(); //将栈顶元素设置为当前位置 int x = temp.x; int y = temp.y; int d = temp.d+1; while(d 8){ int i = x + move[d][0]; int j = y + move[d][1]; if(maze[i][j] == 0){ //该点可达 temp = new Step(i,j,d); //到达新点 s.push(temp); x = i; y = j; maze[x][y] = -1; //到达新点,标志已经到达 if(x == 6 y == 1){ return 1; //到达出口,迷宫有路,返回1 }else{ d = 0; //重新初始化方向 }else{ d++; //改变方向 return 0; }
数据结构 (栈)迷宫求解(c++版本) 理解栈的抽象数据类型定义及操作特点。 掌握顺序栈的存储结构的描述。 掌握顺序栈的基本操作的实现方法。 理解栈的广泛应用。
一开始做这个事觉得很简单,写了之后,发现不对劲,程序陷入了死循环。绝对是有的细节出现的问题,在网上找了找,有的呢是只写了一部分,有的呢是还写错了。最后找到的是c语言版。
相关文章
- SpringBoot整合RabbitMQ 实现五种消息模型 详细教程
- OpenCV-Python实战(1) —— 给图片添加图片水印【利用 OpenCV 像素的读写原理实现】
- 利用vpp和内核协议栈通信机制实现虚拟机上网
- python-协程并发-多任务协程的实现方式(一)
- Linux进程中实现读写锁的方法(linux进程读写锁)
- Linux下实现多网卡路由技术(多网卡路由linux)
- 利用Oracle实现同义词准确删除(oracle同义词删除)
- 以大小排序 Linux: 实现更佳性能(linux大小排序)
- 东京奥运会金牌由废旧家电手机提炼而来:实现百分百再利用
- 利用Oracle排序实现递归(oracle递归排序)
- 策略Java中利用Redis实现数据过期策略(redisjava过期)
- 机制利用Redis实现Java的过期机制(redisjava过期)
- 优化如何利用Oracle数据库实现建表优化(oracle数据库建表)
- 在补丁上戳个洞——利用已经被修复的漏洞实现IE沙箱逃逸
- 利用Linux创建AP热点实现无线网络共享(linuxap热点)
- 利用Oracle Impdp实现数据迁移(oracleimpdp)
- 时间利用Java实现Redis中键值对的超时管理(redisjava过期)
- 集成开发Linux与Qt集成开发:实现无缝交互(linux与qt)
- 处理利用SQL Server实现函数处理的高效率(sqlserver在函数)
- SQL Server互斥试探:当竟然不能实现的时候(sqlserver互斥)
- 利用变量使用变量实现更高效的查询:SQL Server实战指南(sqlserver中如何)
- 利用mssql游标实现变量赋值(mssql 游标赋值)
- Oracle数据库中使用触发器语句实现数据安全管理(oracle中触发器语句)
- 利用 Oracle 中的 SUM 函数实现高效求和(oracle中的求和函数)
- 如何提升Redis性能,实现极致体验(如何提高redis性能)
- 快速构建广播系统利用Redis提升效率(使用redis实现广播)
- 利用Redis集群实现超高性能(redis集群运用)
- 如何高效率利用Oracle实现数据同步(oracle中数据同步)
- 大数据存储压力利用Redis集群,实现高效大数据存储(redis集群如何解决)
- 利用Oracle SQL实现双表全关联查询(oracle两表全关联)
- 如何利用Oracle PCS实现卓越业务变革(oracle pcs)
- Redis利用进程锁实现安全性设置(Redis设置进程锁文件)
- Jquery绑定时间实现代码
- JQuery获取当前屏幕的高度宽度的实现代码
- 可替代log4j日志的c#简单日志类队列实现类代码分享