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

2019 精帖
0 7746

问题描述

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]);
	    }
	}
}



留言(0)
加载更多
猜你喜欢
  • ofc c#方参数传值

    c#方参数传值
  • blog 阻塞及其原理

    1.什么是阻塞 阻塞是一个在基础上又支持了两个附加操作的。2.支持阻塞的插入方满时,会阻塞插入元素的线程,直到不满。1.支持阻塞的移除方空时,获取元素的线程会等待变为非空。2.阻塞
  • blog 使用双向循环链表解决 约瑟夫环-数据结构和

    约瑟夫环描述         有m个人,围成一个环,编号为 1、2、3、、、m,从第一个人开始循环报数(从1开始数),假设数到n的那个人出局,然后从下一个人继续数数(从1开始数),数到n出,以
  • blog 八皇后

    八皇后,是一个古老而著名的,是回溯的典型案例。该是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一或同一斜线上,有多少种摆。1.方
  • blog java内存模型分析-java虚拟机栈最大深

    Java虚拟机栈都包含那些东西         在阅读过深入理解java虚拟机以后了解到java虚拟机栈包括栈帧、局部变量表、操作数栈、动态链接、方返回等。 Java虚拟机栈都储存那些内容呢
  • ofc 图解最短路径-floyd(图的邻接矩阵表示)

    图解最短路径-floyd(图的邻接矩阵表示)
  • blog 枚举案例--熄灯

    熄灯1.描述有一个有按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上下左右)的灯都会改变一次。即(原来亮的变暗,原来暗的变亮)对矩阵中的每一盏灯设置一个初始状态。请你写一
  • blog -数求值

    描述思路: 斐波那契数的变体 考虑如果把20190324项的每一项的值都出来的话,那么值的范围就会超出基本数据类型能够表示的范围,又考虑到目是求最后四位数,而加时前一位不会影响后一位的计结果,例如
  • blog -求和

    描述 给定一个int类型一维数组 a[],和一个int类型的数值 b。编写一个程序,判断数组中有没有两个数(a[i],a[j])的和等于b,如果存在,返回两个数在a数组中的下表(return new int[]={1,2}
  • blog -渗透

    描述: 渗透,给一个n*m的矩阵,0为空白,1为白纸,2为墨水,墨水每经过每一秒会将上下左右相邻的白纸染成黑色,然后继续渗透,判断此图中的白纸最终是否能够全部被墨水染上色,若能需要输出所有白纸全部被墨水染上色的时间。j