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

队列的建立

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

以上就是利用java算法BFS来求迷宫出口最短路径的详细内容，更多内容请关注技术你好其它相关文章！