您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章给大家分享的是有关怎么样使用java算法BFS来求迷宫出口最短路径的内容。小编觉得挺实用的,因此分享给大家做个参考。一起跟随小编过来看看吧。
队列的建立
static Queue r = new LinkedList(); //创建队列
队列的基本方法
r.offer(); 入队尾
r.poll(); 出队首
r.peek(); 队首的内容
代码实现:
全局变量设置
package Two; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BFS { static int a[][] = new int [100][100]; //输入迷宫 static int v[][] = new int [100][100]; //走过的标记为1 static int startx,starty; //输入起点位置 static int p,q; //输入要到达的坐标位置 static int dx[] = {0,1,0,-1}; //方向数组 static int dy[] = {1,0,-1,0}; static Queue<point> r = new LinkedList<point>(); //创建队列 static class point{ //建立类坐标属性 int x; int y; int step; }
输入迷宫和起始位置,目标位置
public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in .nextInt(); for(int i=1;i<=m;i++) //输入迷宫 for(int j=1;j<=n;j++) a[i][j] = in.nextInt(); startx = in.nextInt(); starty = in.nextInt(); //输入目标和起始位置 p = in.nextInt(); q = in.nextInt();
BFS算法开始
1、设置队首
//BFS point start = new point(); //定义一个初始类作为队首 start.x = startx; start.y = starty; start.step = 0; r.offer(start); v[startx][starty]=1;
2、进入循环体
while(!r.isEmpty()) { //当队列为空时跳出循环 int x = r.peek().x; //把队首的属性赋值 int y = r.peek().y; int step = r.peek().step; if(x==p && y==q) { //到达目的地,退出循环 System.out.println(step); break; } for(int i=0;i<4;i++) { //广度遍历,右下左上分别入队 int tx= x+dx[i]; int ty= y+dy[i]; if(a[tx][ty] == 1 && v[tx][ty]==0) { //判断是否可以入队 //入队 point temp = new point(); //建立一个临时类 temp.x = tx; temp.y = ty; temp.step = r.peek().step +1; r.offer(temp); //入队 v[tx][ty]=1; //标记为1 } } r.poll(); //拓展完了需要队首出队 } } }
感谢各位的阅读!关于怎么样使用java算法BFS来求迷宫出口最短路径就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到吧!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。