欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)BFS廣搜法解決迷宮問題

 更新時間:2022年04月06日 14:48:27   作者:求不脫發(fā)  
廣搜BFS的基本思想是: 首先訪問初始點v并將其標志為已經(jīng)訪問。接著通過鄰接關(guān)系將鄰接點入隊。然后每訪問過一個頂點則出隊。按照順序,訪問每一個頂點的所有未被訪問過的頂點直到所有的頂點均被訪問過。廣度優(yōu)先遍歷類似與層次遍歷

1.例題

題目描述

迷宮由 n 行 m 列的單元格組成,每個單元格要么是空地,要么是障礙物。其中1表示空地,可以走通,2表示障礙物。給定起點坐標startx,starty以及終點坐標endx,endy?,F(xiàn)請你找到一條從起點到終點的最短路徑長度。

輸入

第一行包含兩個整數(shù)n,m(1<=n,m<=1000)。接下來 n 行,每行包含m個整數(shù)(值1或2),用于表示這個二維迷宮。接下來一行包含四個整數(shù)startx,starty,endx,endy,分別表示起點坐標和終點坐標。

輸出

如果可以從給定的起點到終點,輸出最短路徑長度,否則輸出NO。?

測試數(shù)據(jù)?

輸入

5 4

1 1 2 1

1 1 1 1

1 1 2 1

1 2 1 1

1 1 1 2

輸出

7

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rGC5LiN6ISx5Y-R,size_20,color_FFFFFF,t_70,g_se,x_16

2. 思路分析

基本思想

這道題屬于一道較為經(jīng)典的BFS圖的廣度優(yōu)先搜索算法例題。類似于一個分層搜索的過程,廣度優(yōu)先搜索需要使用一個隊列以保持訪問過的結(jié)點的順序,以便按這個順序訪問這些結(jié)點的鄰接結(jié)點。即從給定的起點開始向四周擴散,判斷是否能夠到達終點,如果不能,就繼續(xù)BFS廣搜,直到能夠到達終點或者將所有結(jié)點遍歷完一遍。在搜索前定義一個flag變量用來標記是否到達終點。

具體步驟

1)訪問初始結(jié)點 p 并標記結(jié)點 p 為已訪問。

2)結(jié)點 p 入隊列

3)當隊列非空時,繼續(xù)執(zhí)行,否則算法結(jié)束。

4)出隊列取得隊頭結(jié)點 first

5)查找結(jié)點 first 的第一個方向的鄰接結(jié)點 newp 。

6)若結(jié)點 first 的鄰接結(jié)點 newp 不存在,則轉(zhuǎn)到步驟3:否則循環(huán)執(zhí)行以下三個步驟:

  • 6.1若結(jié)點 newp 尚未被訪問并且可以走通,則訪問結(jié)點 newp 并標記為已訪問。
  • 6.2結(jié)點 newp 入隊列
  • 6.3查找結(jié)點 first 的繼 newp 鄰接結(jié)點后的下個鄰接結(jié)點 newp .轉(zhuǎn)到步驟6

代碼實現(xiàn)

import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
	//n*m的地圖,(startx,starty)起點坐標,(endx,endy)終點坐標
	static int n, m, startx, starty, endx, endy;
	static int[][] map;//地圖
	static boolean[][] vistied;//標記當前點是否已經(jīng)走過
	static int[][] step = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	/*
	 * 上下左右移動遍歷搜索 1 ,0 表示 x + 1 ,y + 0 向右移動,其他同理 如果為八向連通 則加上, { 1, 1 }, { 1, -1 }, {
	 * -1, 1 }, { -1, -1 } 代表斜向移動
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n + 2][m + 2];//+2是為了防止點在邊界時,四方向移動造成下標出現(xiàn)-1越界。
		vistied = new boolean[n + 2][m + 2];
		// 錄入數(shù)據(jù)圖  下標(1~n)*(1~m)
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		//錄入起點和終點坐標
		startx = sc.nextInt();
		starty = sc.nextInt();
		endx = sc.nextInt();
		endy = sc.nextInt();
		bfs(startx, starty);//BFS廣搜
	}
 
	private static void bfs(int x, int y) {
		point p = new point(x, y, 0);//初始化point類封裝x,y坐標以及step步數(shù)
		LinkedList<point> queue = new LinkedList<point>();//需要用到的隊列
		queue.add(p);//將當前點入隊列
		vistied[x][y] = true;//標記成已訪問
		boolean flag = false;//是否達到終點標記
		//只要隊列不為空,就說明還有路可走
		while (!queue.isEmpty()) {
			point first = queue.getFirst();//取出隊列的第一個點
			if (first.x == endx && first.y == endy) {//判斷當前點是否與終點坐標重合
				System.out.println(first.step);//打印需要走的步數(shù)
				flag = true;//標記已經(jīng)到達終點
				break;//結(jié)束BFS
			}
			//未到達終點則進行上下左右四個方向移動
			for (int i = 0; i < 4; i++) {
				//橫縱坐標變換實現(xiàn)位置移動
				int newx = first.x + step[i][0];
				int newy = first.y + step[i][1];
				int newstep = first.step + 1;//每一動一次步數(shù)要+1
				//判斷移動后的新位置可以走,并且沒走過
				if (map[newx][newy] == 1 && vistied[newx][newy] == false) {
					point newp = new point(newx, newy, newstep);//封裝數(shù)據(jù)
					queue.add(newp);//入隊列
					vistied[newx][newy] = true;//標記已經(jīng)走過
				}
			}
			queue.removeFirst();//四個方向判斷完成后,要將隊首元素出列
		}
		if (!flag)//如果無法到達終點提示
			System.out.println("NO");
	}
}
//定義一個位置點的class,方便封裝數(shù)據(jù)入隊列
class point {
	int x;
	int y;
	int step;//從起點走到當前點需要走的步數(shù)
 
	public point(int x, int y, int step) {
		this.x = x;
		this.y = y;
		this.step = step;
	}
}

3.BFS小結(jié)

求解思路:

將隊首結(jié)點可拓展的點入隊,如果沒有可拓展的點,將隊首結(jié)點出隊。重復(fù)以上步驟,直到到達目標位置或者隊列為空。

注意

bfs先找到的一定是最短的。但是如果是加權(quán)邊的話這樣就會出問題了,bfs傳回的是經(jīng)過 邊數(shù) 最少的解,但是因為加權(quán)了,這個解到根節(jié)點的 距離 不一定最短。 比如1000+1000是只有兩段,1+1+1+1有4段,由于bfs返回的經(jīng)過邊數(shù)最少的解,這里會返回總長度2000的那個解,顯然不是距離最短的路徑?。BFS 運用到了隊列。

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)BFS廣搜法解決迷宮問題的文章就介紹到這了,更多相關(guān)Java 迷宮問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • java對于目錄下文件的單詞查找操作代碼實現(xiàn)

    java對于目錄下文件的單詞查找操作代碼實現(xiàn)

    這篇文章主要介紹了java對于目錄下文件的單詞查找操作代碼實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-11-11
  • 利用java判斷質(zhì)數(shù)的3種方法代碼示例

    利用java判斷質(zhì)數(shù)的3種方法代碼示例

    這篇文章主要給大家介紹了關(guān)于利用java判斷質(zhì)數(shù)的3種方法,在大于1的整數(shù)中,如果只包含1和本身這兩個約數(shù),就被稱為質(zhì)數(shù)(素數(shù)),文中給出了詳細的代碼示例,需要的朋友可以參考下
    2023-07-07
  • java?Date和SimpleDateFormat時間類詳解

    java?Date和SimpleDateFormat時間類詳解

    這篇文章主要介紹了java?Date和SimpleDateFormat時間類詳解,文章圍繞主題展開詳細的內(nèi)容介紹,具有一定的參考價值,需要的小伙伴可以參考一下
    2022-08-08
  • java中并發(fā)Queue種類與各自API特點以及使用場景說明

    java中并發(fā)Queue種類與各自API特點以及使用場景說明

    這篇文章主要介紹了java中并發(fā)Queue種類與各自API特點以及使用場景說明,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • 永久解決idea git log亂碼的問題

    永久解決idea git log亂碼的問題

    這篇文章主要介紹了永久解決idea git log亂碼的問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-02-02
  • java運行jar包提示?“XXX中沒有主清單屬性”?"找不到主類”兩種解決辦法

    java運行jar包提示?“XXX中沒有主清單屬性”?"找不到主類”兩種解決辦法

    本文主要介紹了java運行jar包提示?“XXX中沒有主清單屬性”?"找不到主類”兩種解決辦法,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • JAVA中Context的詳細介紹和實例分析

    JAVA中Context的詳細介紹和實例分析

    這篇文章主要介紹了JAVA中Context的詳細介紹和實例分析,Context是維持android各組件能夠正常工作的一個核心功能類。如果感興趣來學(xué)習(xí)一下
    2020-07-07
  • 設(shè)置JavaScript自動提示-Eclipse/MyEclipse

    設(shè)置JavaScript自動提示-Eclipse/MyEclipse

    自動提示需要2個組件,分別是:ext-4.0.2a.jsb2||spket-1.6.16.jar,需要的朋友可以參考下
    2016-05-05
  • Java編程實現(xiàn)比對兩個文本文件并標記相同與不同之處的方法

    Java編程實現(xiàn)比對兩個文本文件并標記相同與不同之處的方法

    這篇文章主要介紹了Java編程實現(xiàn)比對兩個文本文件并標記相同與不同之處的方法,涉及java針對文本文件的讀取、遍歷、判斷等相關(guān)操作技巧,需要的朋友可以參考下
    2017-10-10
  • Spring?MVC各種參數(shù)進行封裝的方法實例

    Spring?MVC各種參數(shù)進行封裝的方法實例

    這篇文章主要給大家介紹了關(guān)于Spring?MVC各種參數(shù)進行封裝的相關(guān)資料,SpringMVC內(nèi)置多種數(shù)據(jù)類型轉(zhuǎn)換器,可以根據(jù)請求中的參數(shù)與后端控制器方法的參數(shù)的關(guān)系為我們實現(xiàn)簡單的數(shù)據(jù)封裝,需要的朋友可以參考下
    2023-06-06

最新評論