栈的应用-迷宫问题
1.问题描述:
问题:上面有一个迷宫,灰色部分代表不能通过,白色部分代表可以通过,现在从a点出发,能否找到一条路径到达b点,如果能,输出此路径。
下面采用试探法求解,采用栈结构保存每一步的内容(包括坐标和方向),每前进一步都进行四个方向的试探,如果该方向可以走,就先记录下上一步走过的路径坐标,放进栈中保存,如果四个方向都无法通行,就从栈中取出上一次的路径坐标,换个方向继续试探,直到求解问题。
2.基本算法如下:
(1)在(1,1)进入迷宫,并向正东(v=1)方向试探。
(2)监测下一方位(g,h)。若(g,h)=(m,n)且 maze[m,n]=0,则到达出口,输出走过的路径:程序结束。
(3)若(g,h)≠(m,n),但(g,h)方位能走通且第一次经过则记下这一步,并从(g,h)出发,再向东试探下一步否则仍在(i,j)方位换一个方向试探。
(4)若(,j方位周围4个方位阻塞或已经过,则需退一步并换一个方位试探。若(i,j)=(1,1)则到达入口,说明迷宫走不通。
3.代码演示:
package problem;
public class State {
public int i;//当前位置横坐标
public int j;//当前位置纵坐标
public int getI() {
return i;
}
public State(int i, int j, int v) {
super();
this.i = i;
this.j = j;
this.v = v;
}
public void setI(int i) {
this.i = i;
}
public int getJ() {
return j;
}
public void setJ(int j) {
this.j = j;
}
public int getV() {
return v;
}
public void setV(int v) {
this.v = v;
}
public int v;//当前方向
}
package problem;
import java.util.Stack;
/**
* 栈的应用-迷宫问题
* @author LENOVO
*
*/
public class Maze {
private static int maze[][];//代表迷宫矩阵
private static int mark[][];//标记该坐标是否已经走过
private static int move[][];//方向上的增量(包括四个方向)
public static void main(String[] args) {
move= new int[][] {{0,0},{0,1},{1,0},{0,-1},{-1,0}};
mark=new int[7][7];
maze=new int[][]{{1,1,1,1,1,1,1},
{1,0,0,1,1,0,1},
{1,1,0,0,0,0,1},
{1,1,1,0,1,1,1},
{1,1,1,0,0,0,1},
{1,1,1,0,1,0,1},
{1,1,1,1,1,1,1}};
maze();
}
/**
* 试探
*/
public static void maze() {
//栈,用于保存走每一步的信息,包括每一步的坐标和方向
Stack<State> stack=new Stack<State>();
State s=new State(1, 1, 1);
mark[1][1]=1;
do {
int g=s.i+move[s.v][0],h=s.j+move[s.v][1];
if((g==5&&h==5)&&maze[5][5]==0) {//找到出口
System.out.println("找到出口");
Stack<State> s_=new Stack<State>();
stack.add(s);
while(!stack.isEmpty()) {
s_.add(stack.pop());
}
while(!s_.isEmpty()) {
State l=s_.pop();
System.out.println("坐标:"+l.getI()+"-"+l.getJ());
}
return;
}
if(maze[g][h]==0&&mark[g][h]==0) {//可以向前走
mark[g][h]=1;
stack.add(s);
s=new State(g,h,1);
}else if(s.v<4) {//换个方向试探
s.v++;
}else {//无路可走,返回一步,从栈中取出记录的数据
while(s.v>=4&&!stack.isEmpty()) {
s=stack.pop();
s.v++;
}
}
}while(!stack.isEmpty()&&s.v<=4);//栈不为空,并且还有方向可以试探,则继续试探
System.out.println("没有找到出口");
}
}
move二维数组 的含义是:
横坐标代表方向:1-向右,2-向下,3-向左,4-向上,0-无意义
纵坐标代表位置坐标:0-横坐标,1-纵坐标
值代表该位置上的增量:比如:
move[1,0]=0代表:横坐标向左不变
move[1,1]=1代表:纵坐标向右走1个单位
猜你喜欢
blog
迷宫问题-js实现
数据结构与算法
3106
迷宫问题!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
blog
迷宫问题-寻找最短路径
数据结构与算法
8493
迷宫问题-寻找最短路径算法:广度优先搜索数据结构:队列,链表代码实现:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
blog
栈的应用-表达式求值
数据结构与算法
882
栈的应用-表达式求值1.概念:表达式包括{前缀表达式(波兰式)、中缀表达式、后缀表达式(逆波兰式)}例如:(a+b)*(a-b) 前缀表达式:*+ab-ab 中缀表达式:(a+b)*(a-b) 后缀
blog
算法-迷宫问题-广度优先搜索-队列
数据结构与算法
8290
问题描述思路:典型的广度优先搜索算法,根据字典序大小,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点优先先往下走,然后向左走,然后向右走,然后向上走。则最后首先到达出口的一条路径就是符合
算法基础
350
今天在项目中遇到用"|"分割字符串的问题,如果直接使用下面方式,不会按照我们预想的分割:String[]ids="12|13|14".split("|");分割出来是[1,2,|,1,3,|1,4
java虚拟机(jvm)
5974
象的指针引用,所以一般这部分使用的内存相对较小,而且当方法调用完成以后栈帧中占用的内存即可被回收。影响java虚拟机栈最大深度的因素有那些1.Java虚拟机栈的大小直接影响栈的深度2.在java虚拟机栈
blog
线程的同步问题
java基础
6429
多线程带来的问题:线程有时候回和其他线程共享一些资源,比如内存、数据库等。当多个线程同时读写同一份共享资源的时候,可能会发生冲突。这时候,我们就需要引入线程“同步”机制,即各位线程之间要有顺序使用
数据库
233
是这种写法却隐藏着较深的使用陷阱。在排序字段有数据重复的情况下,会很容易出现排序结果与预期不一致的问题。一、案例mysql版本:mysqlselectversion
最近发表
归档
2018年11月
12
2018年12月
33
2019年01月
28
2019年02月
28
2019年03月
32
2019年04月
27
2019年05月
33
2019年06月
6
2019年07月
12
2019年08月
12
2019年09月
21
2019年10月
8
2019年11月
15
2019年12月
25
2020年01月
9
2020年02月
5
2020年03月
16
2020年04月
4
2020年06月
1
2020年07月
7
2020年08月
13
2020年09月
9
2020年10月
5
2020年12月
3
2021年01月
1
2021年02月
5
2021年03月
7
2021年04月
4
2021年05月
4
2021年06月
1
2021年07月
7
2021年08月
2
2021年09月
8
2021年10月
9
2021年11月
16
2021年12月
14
2022年01月
7
2022年05月
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
目录
祝愿神州十三飞行乘组平安归来