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

问题描述

思路：

        典型的广度优先搜索算法，根据字典序大小，可以确定遍历的循序， 因为字典序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]);
	    }
	}
}