队列的建立
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入门