Heim > Java > JavaErste Schritte > Verwenden Sie den Java-Algorithmus BFS, um den kürzesten Weg zum Labyrinthausgang zu finden

Verwenden Sie den Java-Algorithmus BFS, um den kürzesten Weg zum Labyrinthausgang zu finden

王林
Freigeben: 2020-11-10 15:38:08
nach vorne
2538 Leute haben es durchsucht

Verwenden Sie den Java-Algorithmus BFS, um den kürzesten Weg zum Labyrinthausgang zu finden

Einrichtung einer Warteschlange

static Queue r = new LinkedList(); //创建队列
Nach dem Login kopieren

(Lernvideo-Sharing: Java-Kurs)

Grundlegende Methode der Warteschlange

r.offer(); Geben Sie das Ende der Warteschlange ein

r.poll(); Kopf der Warteschlange

r.peek(); Inhalt des Teamleiters

Code-Implementierung:

Globale Variableneinstellung

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;
	
  }
Nach dem Login kopieren

Geben Sie das Labyrinth und die Startposition ein, Zielposition

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();
Nach dem Login kopieren

BFS-Algorithmus startet

1 der Teamleiter

  //BFS
  point start = new point();   //定义一个初始类作为队首
  start.x = startx;
  start.y = starty;
  start.step = 0;
  r.offer(start);
  v[startx][starty]=1;
Nach dem Login kopieren

2. Treten Sie in die Schleife ein

  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(); //拓展完了需要队首出队
  
  	
  }
  

}
}
Nach dem Login kopieren

Verwandte Empfehlungen: Erste Schritte mit Java

Das obige ist der detaillierte Inhalt vonVerwenden Sie den Java-Algorithmus BFS, um den kürzesten Weg zum Labyrinthausgang zu finden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:csdn.net
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage