文件
专题 ·
最新
首页
  • 我的主页卡化石
  • off中心
  • 基本设置
  • 文件上传

算法-迷宫问题-广度优先搜索-队列

硅谷探秘者 8860 0 0

问题描述

QQ截图20190523185203.png

QQ截图20190523185232.png


思路：

        典型的广度优先搜索算法，根据字典序大小，可以确定遍历的循序， 因为字典序D<L<R<U， 所以对于每一个节点优先先往下走，然后向左走，然后向右走，然后向上走。则最后首先到达出口的一条路径就是符合题意的最短路径。遍历过程中需要一个数组记录遍历的过程，即经过一个节点时，需要记录下是从哪一个节点（或者是以什么方式）到达此节点的。然后利用这个过程关系，可以推出整个过程路径。


代码实现：

package club.test;

public class D {
	static int[][] panel={
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1},
	{1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1},
	{1,0,1,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,1,0,1,1,1},
	{1,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1},
	{1,1,1,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,1,1},
	{1,0,0,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0,0,0,0,0,0,0,1},
	{1,1,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,1},
	{1,0,0,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,1,1},
	{1,1,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,1,0,1,1},
	{1,1,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,1},
	{1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,1,1},
	{1,1,0,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,1,1,0,1,1,0,1,0,0,0,0,1,0,0,0,1},
	{1,1,0,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,0,0,1,1},
	{1,1,0,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,1},
	{1,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,1,1,0,1,0,1,0,0,1,1},
	{1,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,0,0,0,0,1,1,0,1,0,1,1},
	{1,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,1,0,1},
	{1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,1},
	{1,1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,1,1,0,1,1,0,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,1},
	{1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,1},
	{1,1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,0,1},
	{1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1},
	{1,1,1,0,1,0,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,0,1},
	{1,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,1,1,0,0,1,1,1},
	{1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1},
	{1,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1},
	{1,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1,1},
	{1,1,0,0,0,0,0,0,1,1,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,1,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
}
package club.test;

import java.util.LinkedList;
/**
 * 迷宫问题
 * @author jiajia
 */
public class TestMain10 {
	/**
	 * 记录节点位置
	 */
	public static class Location{
		public int x;
		public int y;
		public Location(int x,int y){
			this.x=x;
			this.y=y;
		}
	}
	/**
	 * 字典序D<L<R<U
	 * 所以对于每一个节点优先先往下走，然后向左走，然后向右走，然后向上走
	 *对应的方位增量为move[][]数组
	 */
	static int move[][] = { {1,0}, {0,-1}, {0,1}, {-1,0} };
	
	/**
	 * 路径数组
	 */
	static int panel[][]=D.panel;
	/**
	 * 所经过的路径标记
	 *数组中多定义了两行两列
	 *首行，尾行，和首列尾列都是1，代表不可达。
	 */
	static int role[][]=new int[32][52];
	/**
	 * 方向
	 */
	static char[] c=new char[]{'D','L','R','U'};
	/**
	 * 队列，储存待遍历节点
	 */
	static LinkedList<Location> qu=new LinkedList<Location>();
	/**
	 * 主函数
	 */
	public static void main(String[] args) {
		long l=System.currentTimeMillis();
		bfs();
		long l2=System.currentTimeMillis();
		System.out.println();
		System.out.println(l2-l);
	}
	/**
	 * 寻路
	 */
	public static void bfs() {
		/**
		 * 添加第一个元素
		 */
		panel[1][1] =1;
		qu.offer(new Location(1,1));
		/**
		 * 广度优先搜索的过程
		 *如果队列不为空，则一直循环
		 */
		while(!qu.isEmpty()) {
			/**
			 * 从队列中
			 */
			Location l=qu.poll();
			/**
			 * 已经到达出口
			 */
			if(l.x==30&&l.y==50) 
				break; 			 
			/**
			 * 按照D<L<R<U遍历该节点的四个方向
			 */
			for (int i = 0; i < 4; ++i) {
				/**
				 * nx,ny是待遍历节点的坐标
				 */
				int nx=l.x+move[i][0],ny=l.y+move[i][1];
				/**
				 * 判断该节点有没有走过
				 *如果是0则没有走过，可以进行前进，将其状态置为1，代表已经走过
				 *然后将该节点入队
				 */
				if (panel[nx][ny] == 0) {
					panel[nx][ny] = 1;
	                qu.offer(new Location(nx, ny));
	                /**
	                 * 记录经过该节点时的状态，即从那个方位过来的
	                 */
	                role[nx][ny] = i;
	            }
			}
		}
		dfs(30,50);
	}
	/**
	 * 深度优先搜索
	 * 打印路径
	 */
	public static void dfs(int x,int y) {
		/**
		 * 因为在寻路的过程中把经过每一个节点的状态给记录在role数组中，
		 * 所以根据每个节点的状态可以推导出之前的状态。
		 */
		if (x != 1 || y != 1) {
	        int t = role[x][y];
	        /**
	         * t代表是通过第t种方位增量到达x，y节点的，
	         * 所以可以通过这种增量状态，和x,y节点推导出之前的系节点位置
	         */
	        dfs(x - move[t][0], y - move[t][1]);
	        System.out.print(c[t]);
	    }
	}
}



猜你喜欢
数据结构与算法 8992 迷宫问题-寻找最短路径算法：广度优先搜索数据结构：队列，链表代码实现：!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
数据结构与算法 2183 广度优先搜索算法（dfs、深搜）java实现-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图的数据结构：则用邻接矩阵表示为： privatestaticintmap[][]={ {0,3,6
数据结构与算法 2344 上一篇：广度优先搜索算法（bfs、广搜）java实现-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图数据结构则用邻接矩阵表示为： privatestaticintmap
official 1339 《操作系统》时间片轮转算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在
数据结构与算法 3644 迷宫问题!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
数据结构与算法 8248 1.问题描述：问题：上面有一个迷宫，灰色部分代表不能通过，白色部分代表可以通过，现在从a点出发，能否找到一条路径到达b点，如果能，输出此路径。下面采用试探法求解，采用栈结构保存每一步的内容（包括坐标
数据结构与算法 4420 优先级队列普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（firstin
weblog 2661 了解优先级队列的详细叙述请访问(java实现):java用数组实现优先级队列（小顶堆） 实验目的: 先按key优先，如果key值相等再按value.hg优先。 插入数据案例
最近发表
归档
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 2022年10月  2 2022年12月  5 2023年01月  3 2023年02月  1 2023年03月  4 2023年04月  2 2023年06月  3 2023年07月  4 2023年08月  1 2023年10月  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript
目录
没有一个冬天不可逾越，没有一个春天不会来临。最慢的步伐不是跬步，而是徘徊，最快的脚步不是冲刺，而是坚持。