栈的应用-迷宫问题

硅谷探秘者 7762 0 0

1.问题描述:

image.png

问题:上面有一个迷宫,灰色部分代表不能通过,白色部分代表可以通过,现在从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个单位


猜你喜欢
数据结构与算法 3106 !DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
数据结构与算法 8493 -寻找最短路径算法:广度优先搜索数据结构:队列,链表代码实现:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
数据结构与算法 882 -表达式求值1.概念:表达式包括{前缀表达式(波兰式)、中缀表达式、后缀表达式(逆波兰式)}例如:(a+b)*(a-b) 前缀表达式:*+ab-ab 中缀表达式:(a+b)*(a-b) 后缀
数据结构与算法 8290 描述思路:典型广度优先搜索算法,根据字典序大小,可以确定遍历循序,因为字典序DLRU,所以对于每一个节点优先先往下走,然后向左走,然后向右走,然后向上走。则最后首先到达出口一条路径就是符合
算法基础 350 今天在项目中遇到"|"分割字符串,如果直接使下面方式,不会按照我们预想分割:String[]ids="12|13|14".split("|");分割出来是[1,2,|,1,3,|1,4
java虚拟机(jvm) 5974 指针引,所以一般这部分使内存相对较小,而且当方法调完成以后帧中占内存即可被回收。影响java虚拟机最大深度因素有那些1.Java虚拟机大小直接影响深度2.在java虚拟机
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
目录
祝愿神州十三飞行乘组平安归来