Java數(shù)據(jù)結構BFS廣搜法解決迷宮問題
1.例題
題目描述
迷宮由 n 行 m 列的單元格組成,每個單元格要么是空地,要么是障礙物。其中1表示空地,可以走通,2表示障礙物。給定起點坐標startx,starty以及終點坐標endx,endy。現(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

2. 思路分析
基本思想
這道題屬于一道較為經(jīng)典的BFS圖的廣度優(yōu)先搜索算法例題。類似于一個分層搜索的過程,廣度優(yōu)先搜索需要使用一個隊列以保持訪問過的結點的順序,以便按這個順序訪問這些結點的鄰接結點。即從給定的起點開始向四周擴散,判斷是否能夠到達終點,如果不能,就繼續(xù)BFS廣搜,直到能夠到達終點或者將所有結點遍歷完一遍。在搜索前定義一個flag變量用來標記是否到達終點。
具體步驟
1)訪問初始結點 p 并標記結點 p 為已訪問。
2)結點 p 入隊列
3)當隊列非空時,繼續(xù)執(zhí)行,否則算法結束。
4)出隊列取得隊頭結點 first
5)查找結點 first 的第一個方向的鄰接結點 newp 。
6)若結點 first 的鄰接結點 newp 不存在,則轉(zhuǎn)到步驟3:否則循環(huán)執(zhí)行以下三個步驟:
- 6.1若結點 newp 尚未被訪問并且可以走通,則訪問結點 newp 并標記為已訪問。
- 6.2結點 newp 入隊列
- 6.3查找結點 first 的繼 newp 鄰接結點后的下個鄰接結點 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;//結束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小結
求解思路:
將隊首結點可拓展的點入隊,如果沒有可拓展的點,將隊首結點出隊。重復以上步驟,直到到達目標位置或者隊列為空。
注意
bfs先找到的一定是最短的。但是如果是加權邊的話這樣就會出問題了,bfs傳回的是經(jīng)過 邊數(shù) 最少的解,但是因為加權了,這個解到根節(jié)點的 距離 不一定最短。 比如1000+1000是只有兩段,1+1+1+1有4段,由于bfs返回的經(jīng)過邊數(shù)最少的解,這里會返回總長度2000的那個解,顯然不是距離最短的路徑?。BFS 運用到了隊列。
到此這篇關于Java數(shù)據(jù)結構BFS廣搜法解決迷宮問題的文章就介紹到這了,更多相關Java 迷宮問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
springboot加載命令行參數(shù)ApplicationArguments的實現(xiàn)
本文主要介紹了springboot加載命令行參數(shù)ApplicationArguments的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-04-04
springboot整合logback實現(xiàn)日志管理操作
本章節(jié)是記錄logback在springboot項目中的簡單使用,本文將會演示如何通過logback將日志記錄到日志文件或輸出到控制臺等管理操作,感興趣的朋友跟隨小編一起看看吧2024-02-02

