Problem Description
　　給定一個m × n (m行, n列)的迷宮，迷宮中有兩個位置，gloria想從迷宮的一個位置走到另外一個位置，當(dāng)然迷宮中有些地方是空地，gloria可以穿越，有些地方是障礙，她必須繞行，從迷宮的一個位置，只能走到與它相鄰的4個位置中,當(dāng)然在行走過程中，gloria不能走到迷宮外面去。令人頭痛的是，gloria是個沒什么方向感的人，因此，她在行走過程中，不能轉(zhuǎn)太多彎了，否則她會暈倒的。我們假定給定的兩個位置都是空地，初始時，gloria所面向的方向未定，她可以選擇4個方向的任何一個出發(fā)，而不算成一次轉(zhuǎn)彎。gloria能從一個位置走到另外一個位置嗎？
Input
　　第1行為一個整數(shù)t (1 ≤ t ≤ 100),表示測試數(shù)據(jù)的個數(shù)，接下來為t組測試數(shù)據(jù)，每組測試數(shù)據(jù)中，
　　第1行為兩個整數(shù)m, n (1 ≤ m, n ≤ 100),分別表示迷宮的行數(shù)和列數(shù)，接下來m行，每行包括n個字符，其中字符’.‘表示該位置為空地，字符’*'表示該位置為障礙，輸入數(shù)據(jù)中只有這兩種字符，每組測試數(shù)據(jù)的最后一行為5個整數(shù)k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能轉(zhuǎn)的彎數(shù)，(x1, y1), (x2, y2)表示兩個位置，其中x1，x2對應(yīng)列，y1, y2對應(yīng)行。
Output
　　每組測試數(shù)據(jù)對應(yīng)為一行，若gloria能從一個位置走到另外一個位置，輸出“yes”，否則輸出“no”。
Sample Input
2
5 5
…**
*..
…
…
…
1 1 1 1 3
5 5
…
*.*.
…
…
*…
2 1 1 1 3
Sample Output
no
yes
首先論對寬搜的認(rèn)識，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前，一直看不懂什么是寬搜，當(dāng)時遇到搜索題很是苦惱，只會用回溯法進(jìn)行深搜，還是利用到了函數(shù)運(yùn)行的機(jī)制（類似遞歸），第一次真正明白寬搜的運(yùn)行機(jī)制是二叉樹的遍歷，有一種用隊列的遍歷方式（二叉樹鏈接）才明白寬搜的運(yùn)行機(jī)制，面對這題，深搜超時，可能有的大神優(yōu)化能過。但是首先想到的應(yīng)該是寬搜，核心點(diǎn)是轉(zhuǎn)彎的次數(shù)。
1：剛開始我打算用boolean數(shù)組標(biāo)記走過的位置，用class新類time表示點(diǎn)的轉(zhuǎn)彎次數(shù)，后來錯了。想了一想錯的原因，右下右轉(zhuǎn)兩次，如果下右右只有一次但是晚走而沒法走，所以這種想法是錯的。
2：用數(shù)組標(biāo)記當(dāng)前點(diǎn)的最小轉(zhuǎn)彎，如果新點(diǎn)，入隊。若果比這個點(diǎn)的轉(zhuǎn)彎次小于等于，也可以入隊。這樣就能保證最終找到最終答案，但是還是不過，超時。至于原因：樓梯模型（要克服樓梯的走樓梯而不直走的問題）
3：最終處理方案:使用優(yōu)先隊列，（java的需要自己百度學(xué)習(xí)一下），因為漫天都是C類的代碼，教程，我根本不知道那個是優(yōu)先隊列。必須用優(yōu)先隊列優(yōu)化。后來請教了學(xué)長幫我解決。優(yōu)先隊列讓小節(jié)點(diǎn)先 入隊。
wa了28次，第29次終于過了。
代碼如下：

import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; /** bfs 標(biāo)記節(jié)點(diǎn)，計入最小節(jié)點(diǎn) 優(yōu)先隊列優(yōu)化*/ public class 杭電1728bfs {static int a[][]= {{-1,0},{0,1},{1,0},{0,-1}};//左 上 右 下static boolean judgle=false;public static void main(String[] args) { Scanner sc=new Scanner(System.in);int t=sc.nextInt(); //測試數(shù)據(jù) for(int t1=0;t1 q1=new PriorityQueue<>(timecomepare);e[y][x]=-1;q1.add(new zuobiao(x,y)); while(!q1.isEmpty()){zuobiao exa=q1.peek();//頭坐標(biāo)q1.poll();int x1=exa.x;int y1=exa.y;if(x1==x2&&y1==y2){if(exa.time<=k) {judgle=true;break;}} elsefor(int i=0;i<4;i ){if(x1 a[i][0]<0||x1 a[i][0]>n-1||y1 a[i][1]<0||y1 a[i][1]>m-1||c[y1 a[i][1]][x1 a[i][0]]==false){}//不能走或者走過 else {zuobiao zuo=new zuobiao(x1 a[i][0],y1 a[i][1],exa.time,exa.fangxiang);zuo.fangxiang=i;if(zuo.fangxiang!=exa.fangxiang) {zuo.time ;}if(e[y1 a[i][1]][x1 a[i][0]]>=zuo.time)//轉(zhuǎn)頭次數(shù)小于等于，入隊{q1.add(zuo);e[y1 a[i][1]][x1 a[i][0]]=zuo.time;} else if(e[y1 a[i][1]][x1 a[i][0]]==0){//初始的沒用過，入隊q1.add(zuo);e[y1 a[i][1]][x1 a[i][0]]=zuo.time; } } }}}public static Comparator timecomepare =new Comparator()//實現(xiàn)comparator接口{public int compare(zuobiao a1,zuobiao a2){return (int)(a1.time-a2.time);}}; } class zuobiao {int x;int y;int time;int fangxiang;public zuobiao(int x,int y){this.x=x;this.y=y;this.fangxiang=-1;this.time=-1;}public zuobiao(int x,int y,int time,int fangxiang){this.x=x;this.y=y;this.time=time;this.fangxiang=fangxiang;}}

不知道有什么不妥或者不對的地方。請大神更正

總結(jié)

以上是生活随笔為你收集整理的杭电1728bfs逃离迷宫java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。