怎么樣使用java算法BFS來求迷宮出口最短路徑

這篇文章給大家分享的是有關(guān)怎么樣使用java算法BFS來求迷宮出口最短路徑的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考。一起跟隨小編過來看看吧。

隊(duì)列的建立

static Queue r = new LinkedList(); //創(chuàng)建隊(duì)列

隊(duì)列的基本方法

r.offer(); 入隊(duì)尾

r.poll(); 出隊(duì)首

r.peek(); 隊(duì)首的內(nèi)容

代碼實(shí)現(xiàn)：

全局變量設(shè)置

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]; //走過的標(biāo)記為1
  static int startx,starty;    //輸入起點(diǎn)位置
  static int p,q;      //輸入要到達(dá)的坐標(biāo)位置
  static int dx[] = {0,1,0,-1};  //方向數(shù)組
  static int dy[] = {1,0,-1,0}; 
  
  static Queue<point> r = new LinkedList<point>();  //創(chuàng)建隊(duì)列
  
  
  static class point{     //建立類坐標(biāo)屬性
	  int x;
	  int y;
	  int step;
	
  }

輸入迷宮和起始位置，目標(biāo)位置

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();    //輸入目標(biāo)和起始位置
  p = in.nextInt();
  q = in.nextInt();

BFS算法開始

1、設(shè)置隊(duì)首

  //BFS
  point start = new point();   //定義一個(gè)初始類作為隊(duì)首
  start.x = startx;
  start.y = starty;
  start.step = 0;
  r.offer(start);
  v[startx][starty]=1;

2、進(jìn)入循環(huán)體

  while(!r.isEmpty()) {        //當(dāng)隊(duì)列為空時(shí)跳出循環(huán)
  	
  	int x = r.peek().x;      //把隊(duì)首的屬性賦值
  	int y = r.peek().y;
  	int step = r.peek().step;
  	
  	
  	if(x==p && y==q) {           //到達(dá)目的地，退出循環(huán)
  		System.out.println(step);
  		break;
  	}
  	
  	for(int i=0;i<4;i++) {       //廣度遍歷，右下左上分別入隊(duì)
  		int tx= x+dx[i];
  		int ty= y+dy[i];
  	

  		if(a[tx][ty] == 1 && v[tx][ty]==0) {   //判斷是否可以入隊(duì)
  			//入隊(duì)
  			point temp = new point();    //建立一個(gè)臨時(shí)類
  			temp.x = tx;
  			temp.y = ty;
  			temp.step = r.peek().step +1;
  			
  	
  			r.offer(temp);     //入隊(duì)
  			v[tx][ty]=1;       //標(biāo)記為1
  		}
  	}
  	
  	r.poll(); //拓展完了需要隊(duì)首出隊(duì)
  
  	
  }
  

}
}

感謝各位的閱讀！關(guān)于怎么樣使用java算法BFS來求迷宮出口最短路徑就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！