算法-迷宫问题-广度优先搜索-队列
问题描述
思路：
典型的广度优先搜索算法，根据字典序大小，可以确定遍历的循序， 因为字典序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]);
}
}
}
猜你喜欢
blog
迷宫问题-寻找最短路径
数据结构与算法
8602
迷宫问题-寻找最短路径算法：广度优先搜索数据结构：队列，链表代码实现：!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script
数据结构与算法
1490
广度优先搜索算法（dfs、深搜）java实现-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图的数据结构：则用邻接矩阵表示为： privatestaticintmap[][]={ {0,3,6
数据结构与算法
1490
上一篇：广度优先搜索算法（bfs、广搜）java实现-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图数据结构则用邻接矩阵表示为： privatestaticintmap
official
745
《操作系统》时间片轮转算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在
blog
迷宫问题-js实现
数据结构与算法
3230
迷宫问题!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
blog
栈的应用-迷宫问题
数据结构与算法
7878
1.问题描述：问题：上面有一个迷宫，灰色部分代表不能通过，白色部分代表可以通过，现在从a点出发，能否找到一条路径到达b点，如果能，输出此路径。下面采用试探法求解，采用栈结构保存每一步的内容（包括坐标
blog
java用数组实现优先级队列（小顶堆）
数据结构与算法
3412
优先级队列普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（firstin
weblog
1761
了解优先级队列的详细叙述请访问(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
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
mysql
ensp
网络基础
目录
余生别太较劲，放过自己 才会幸福。