利用java算法BFS来求迷宫出口最短路径

队列的建立static Queue r = new LinkedList(); //创建队列(学习视频分享:java课程)队列的基本方法r.offer(); 入队尾r.poll(); 出队首r.pee

队列的建立

static Queue r = new LinkedList(); //创建队列

(学习视频分享:java课程)

队列的基本方法

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入门

关于作者: 营销实力派

为您推荐

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注