最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

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

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

1.例題

題目描述

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

輸入

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

輸出

如果可以從給定的起點(diǎn)到終點(diǎn),輸出最短路徑長(zhǎng)度,否則輸出NO。?

測(cè)試數(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)先搜索算法例題。類似于一個(gè)分層搜索的過(guò)程,廣度優(yōu)先搜索需要使用一個(gè)隊(duì)列以保持訪問(wèn)過(guò)的結(jié)點(diǎn)的順序,以便按這個(gè)順序訪問(wèn)這些結(jié)點(diǎn)的鄰接結(jié)點(diǎn)。即從給定的起點(diǎn)開(kāi)始向四周擴(kuò)散,判斷是否能夠到達(dá)終點(diǎn),如果不能,就繼續(xù)BFS廣搜,直到能夠到達(dá)終點(diǎn)或者將所有結(jié)點(diǎn)遍歷完一遍。在搜索前定義一個(gè)flag變量用來(lái)標(biāo)記是否到達(dá)終點(diǎn)。

具體步驟

1)訪問(wèn)初始結(jié)點(diǎn) p 并標(biāo)記結(jié)點(diǎn) p 為已訪問(wèn)。

2)結(jié)點(diǎn) p 入隊(duì)列

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

4)出隊(duì)列取得隊(duì)頭結(jié)點(diǎn) first

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

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

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

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

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

3.BFS小結(jié)

求解思路:

將隊(duì)首結(jié)點(diǎn)可拓展的點(diǎn)入隊(duì),如果沒(méi)有可拓展的點(diǎn),將隊(duì)首結(jié)點(diǎn)出隊(duì)。重復(fù)以上步驟,直到到達(dá)目標(biāo)位置或者隊(duì)列為空。

注意

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

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

相關(guān)文章

  • 熟練掌握J(rèn)ava8新特性之Stream API的全面應(yīng)用

    熟練掌握J(rèn)ava8新特性之Stream API的全面應(yīng)用

    Stream是Java8的一大亮點(diǎn),是對(duì)容器對(duì)象功能的增強(qiáng),它專注于對(duì)容器對(duì)象進(jìn)行各種非常便利、高效的 聚合操作(aggregate operation)或者大批量數(shù)據(jù)操作。Stream API借助于同樣新出現(xiàn)的Lambda表達(dá)式,極大的提高編程效率和程序可讀性,感興趣的朋友快來(lái)看看吧
    2021-11-11
  • java中mybatis和hibernate的用法總結(jié)

    java中mybatis和hibernate的用法總結(jié)

    在本篇文章里小編給大家整理的是一篇關(guān)于java中mybatis和hibernate的用法總結(jié)內(nèi)容,有興趣的朋友們可以學(xué)習(xí)參考下。
    2021-01-01
  • java實(shí)現(xiàn)抖音代碼舞源碼

    java實(shí)現(xiàn)抖音代碼舞源碼

    這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)抖音代碼舞的方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-04-04
  • Java中List與Map初始化的一些寫(xiě)法分享

    Java中List與Map初始化的一些寫(xiě)法分享

    這篇文章主要介紹了Java中List與Map初始化的一些寫(xiě)法有需要的朋友可以參考一下
    2014-01-01
  • java判斷字符串是否有逗號(hào)的方法

    java判斷字符串是否有逗號(hào)的方法

    下面小編就為大家?guī)?lái)一篇java判斷字符串是否有逗號(hào)的方法。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2016-11-11
  • springboot加載命令行參數(shù)ApplicationArguments的實(shí)現(xiàn)

    springboot加載命令行參數(shù)ApplicationArguments的實(shí)現(xiàn)

    本文主要介紹了springboot加載命令行參數(shù)ApplicationArguments的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2023-04-04
  • SpringBoot整合JPA框架實(shí)現(xiàn)過(guò)程講解

    SpringBoot整合JPA框架實(shí)現(xiàn)過(guò)程講解

    在開(kāi)發(fā)中,我們通常會(huì)對(duì)數(shù)據(jù)庫(kù)的數(shù)據(jù)進(jìn)行操作,Sprirng?Boot對(duì)關(guān)系型數(shù)據(jù)庫(kù)和非關(guān)系型數(shù)據(jù)庫(kù)的訪問(wèn)操作都提供了非常好的整合支持
    2022-12-12
  • springboot相關(guān)面試題匯總詳解

    springboot相關(guān)面試題匯總詳解

    這篇文章主要介紹了springboot相關(guān)面試題匯總詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-08-08
  • springboot整合logback實(shí)現(xiàn)日志管理操作

    springboot整合logback實(shí)現(xiàn)日志管理操作

    本章節(jié)是記錄logback在springboot項(xiàng)目中的簡(jiǎn)單使用,本文將會(huì)演示如何通過(guò)logback將日志記錄到日志文件或輸出到控制臺(tái)等管理操作,感興趣的朋友跟隨小編一起看看吧
    2024-02-02
  • Mybatis實(shí)現(xiàn)增刪改查(CRUD)實(shí)例代碼

    Mybatis實(shí)現(xiàn)增刪改查(CRUD)實(shí)例代碼

    MyBatis 是支持普通 SQL 查詢,存儲(chǔ)過(guò)程和高級(jí)映射的優(yōu)秀持久層框架。通過(guò)本文給大家介紹Mybatis實(shí)現(xiàn)增刪改查(CRUD)實(shí)例代碼 ,需要的朋友參考下
    2016-05-05

最新評(píng)論

克山县| 南皮县| 确山县| 布拖县| 宁强县| 秦皇岛市| 东明县| 华安县| 勃利县| 清河县| 留坝县| 崇阳县| 绵竹市| 山西省| 海丰县| 施秉县| 马龙县| 买车| 府谷县| 永胜县| 探索| 眉山市| 夏邑县| 宁波市| 阿巴嘎旗| 新化县| 临洮县| 胶州市| 新兴县| 鲁甸县| 伊宁市| 类乌齐县| 文安县| 偏关县| 房产| 成安县| 正定县| 太白县| 水城县| 澎湖县| 美姑县|