Java數(shù)據(jù)結(jié)構(gòu)BFS廣搜法解決迷宮問(wèn)題
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
2. 思路分析
基本思想
這道題屬于一道較為經(jīng)典的BFS圖的廣度優(yōu)先搜索算法例題。類(lèi)似于一個(gè)分層搜索的過(guò)程,廣度優(yōu)先搜索需要使用一個(gè)隊(duì)列以保持訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)的順序,以便按這個(gè)順序訪(fǎng)問(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)訪(fǎng)問(wèn)初始結(jié)點(diǎn) p 并標(biāo)記結(jié)點(diǎn) p 為已訪(fǎng)問(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 尚未被訪(fǎng)問(wèn)并且可以走通,則訪(fǎng)問(wèn)結(jié)點(diǎn) newp 并標(biāo)記為已訪(fǎng)問(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類(lèi)封裝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)記成已訪(fǎng)問(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à)這樣就會(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)文章
java對(duì)于目錄下文件的單詞查找操作代碼實(shí)現(xiàn)
這篇文章主要介紹了java對(duì)于目錄下文件的單詞查找操作代碼實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11java?Date和SimpleDateFormat時(shí)間類(lèi)詳解
這篇文章主要介紹了java?Date和SimpleDateFormat時(shí)間類(lèi)詳解,文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下2022-08-08java中并發(fā)Queue種類(lèi)與各自API特點(diǎn)以及使用場(chǎng)景說(shuō)明
這篇文章主要介紹了java中并發(fā)Queue種類(lèi)與各自API特點(diǎn)以及使用場(chǎng)景說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-06-06java運(yùn)行jar包提示?“XXX中沒(méi)有主清單屬性”?"找不到主類(lèi)”兩種解決辦法
本文主要介紹了java運(yùn)行jar包提示?“XXX中沒(méi)有主清單屬性”?"找不到主類(lèi)”兩種解決辦法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06JAVA中Context的詳細(xì)介紹和實(shí)例分析
這篇文章主要介紹了JAVA中Context的詳細(xì)介紹和實(shí)例分析,Context是維持android各組件能夠正常工作的一個(gè)核心功能類(lèi)。如果感興趣來(lái)學(xué)習(xí)一下2020-07-07設(shè)置JavaScript自動(dòng)提示-Eclipse/MyEclipse
自動(dòng)提示需要2個(gè)組件,分別是:ext-4.0.2a.jsb2||spket-1.6.16.jar,需要的朋友可以參考下2016-05-05Java編程實(shí)現(xiàn)比對(duì)兩個(gè)文本文件并標(biāo)記相同與不同之處的方法
這篇文章主要介紹了Java編程實(shí)現(xiàn)比對(duì)兩個(gè)文本文件并標(biāo)記相同與不同之處的方法,涉及java針對(duì)文本文件的讀取、遍歷、判斷等相關(guān)操作技巧,需要的朋友可以參考下2017-10-10Spring?MVC各種參數(shù)進(jìn)行封裝的方法實(shí)例
這篇文章主要給大家介紹了關(guān)于Spring?MVC各種參數(shù)進(jìn)行封裝的相關(guān)資料,SpringMVC內(nèi)置多種數(shù)據(jù)類(lèi)型轉(zhuǎn)換器,可以根據(jù)請(qǐng)求中的參數(shù)與后端控制器方法的參數(shù)的關(guān)系為我們實(shí)現(xiàn)簡(jiǎn)單的數(shù)據(jù)封裝,需要的朋友可以參考下2023-06-06