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

硅谷探秘者 8053 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]);
	    }
	}
}



猜你喜欢
数据结构与算法 8305 -寻找最短路径广数据结构:,链表代码实现:!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
数据结构与算法 799 广(dfs、深)java实现-数据结构和用邻接矩阵表示图的定点之间的关系如下图的数据结构:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
数据结构与算法 835 上一篇:广(bfs、广)java实现-数据结构和用邻接矩阵表示图的定点之间的关系如下图数据结构则用邻接矩阵表示为: privatestaticintmap
official 183 《操作系统》时间片轮转思想:公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应规则:按照各进程到达就绪的顺序,轮流让各个进程执行一个时间片(如100ms)。若进程未在
数据结构与算法 2859 !DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
数据结构与算法 7583 1.描述::上面有一个,灰色部分代表不能通过,白色部分代表可以通过,现在从a点出发,能否找到一条路径到达b点,如果能,输出此路径。下面采用试探求解,采用栈结构保存每一步的内容(包括坐标
数据结构与算法 2721 普通的是一种出的数据结构,元素在尾追加,而从头删除。在中,元素被赋予级。当访元素时,具有最高级的元素最删除。具有最高级出(firstin
weblog 1134 了解的详细叙述请访(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
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo
目录