栈的应用-迷宫问题

硅谷探秘者 7877 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个单位


猜你喜欢
数据结构与算法 3230 !DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
数据结构与算法 8602 -寻找最短路径算法:广度优先搜索数据结构:队列,链表代码实现:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
数据结构与算法 981 -表达式求值1.概念:表达式包括{前缀表达式(波兰式)、中缀表达式、后缀表达式(逆波兰式)}例如:(a+b)*(a-b) 前缀表达式:*+ab-ab 中缀表达式:(a+b)*(a-b) 后缀
数据结构与算法 8439 描述思路:典型广度优先搜索算法,根据字典序大小,可以确定遍历循序,因为字典序DLRU,所以对于每一个节点优先先往下走,然后向左走,然后向右走,然后向上走。则最后首先到达出口一条路径就是符合
算法基础 446 今天在项目中遇到"|"分割字符串,如果直接使下面方式,不会按照我们预想分割:String[]ids="12|13|14".split("|");分割出来是[1,2,|,1,3,|1,4
java虚拟机(jvm) 6137 指针引,所以一般这部分使内存相对较小,而且当方法调完成以后帧中占内存即可被回收。影响java虚拟机最大深度因素有那些1.Java虚拟机大小直接影响深度2.在java虚拟机
java基础 6570 多线程带来:线程有时候回和其他线程共享一些资源,比如内存、数据库等。当多个线程同时读写同一份共享资源时候,可能会发生冲突。这时候,我们就需要引入线程“同步”机制,即各位线程之间要有顺序使
数据库 345 是这种写法却隐藏着较深使陷阱。在排序字段有数据重复情况下,会很容易出现排序结果与预期不一致。一、案例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 2022年08月  3 2022年09月  2
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础
目录
余生别太较劲,放过自己 才会幸福。