Nightmare
問題描述
伊格內修斯昨晚有一場噩夢。他發現自己身陷迷宮，身上有一枚定時炸彈。迷宮有一個出口，在炸彈爆炸之前，伊格內修斯應該走出迷宮。炸彈的最初爆炸時間設定為6分鐘。為了防止炸彈爆炸，伊格內修斯必須緩慢移動，即從一個區域移動到最近的區域（也就是說，如果Ignatius現在站在（x，y）上，他只能在（x 1， y），（x-1，y），（x，y 1）或（x，y-1））在1分鐘內。迷宮中的某個區域包含一個炸彈重置設備。他們可以將爆炸時間重置為6分鐘。

鑒于迷宮布局和伊格內修斯的起始位置，請告訴伊格納修斯他是否可以走出迷宮，如果可以的話，輸出他必須用來尋找迷宮出口的最短時間，否則輸出-1。

以下是一些規則：
我們可以假設迷宮是2陣列。
2.每分鐘，伊格內修斯都只能到最近的一個地方，他不應該走出邊界，當然他也不能在墻上行走。
3.如果伊格內修斯在爆炸時間變為0時到達出口處，他就無法離開迷宮。
4.如果伊格內修斯在爆炸時間變為0時到達包含炸彈休息裝備的區域，他不能使用該裝備重置炸彈。
5.炸彈重置設備可以根據需要多次使用，如果需要的話，伊格內修斯可以根據需要多次進入迷宮中的任何區域。
6.重置爆炸時間的時間可以忽略，換句話說，如果伊格內修斯到達包含炸彈休息裝備的區域，并且爆炸時間大于0，則爆炸時間將重置為6。

輸入
輸入包含多個測試用例。輸入的第一行是單個整數T，它是測試用例的數量。 T測試用例如下。
每個測試用例都以兩個表示迷宮大小的整數N和M（1 <= N，Mm = 8）開始。然后N行，每行包含M個整數。該數組表示迷宮的布局。
有五個整數表示迷宮中不同類型的區域：
0：該地區是一堵墻，伊格內修斯不應該走上它。
1：該地區沒有任何東西，伊格內修斯可以在其上行走。
2：伊格內修斯的起跑位置，伊格內修斯開始逃離這個位置。
3：迷宮的出口，依納爵的目標位置。
4：該區域包含一個炸彈重置設備，Ignatius可以通過步行到這些區域來延遲爆炸時間。

產量
對于每個測試案例，如果Ignatius可以走出迷宮，那么你應該輸出他需要的最短時間，否則你應該輸出-1。

示例輸入
3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1

示例輸出
4
-1
13
要求找到最小的走路次數值，并且用深搜無法剪枝，顯然是一道寬搜題。有一些注意點：
1：普通的位置可以走多次，不需要標記，因為有可能就為了去吃重置炸彈的裝置就再某個邊角地方進去一下出來一下。
2：重置的點需要標記，因為重置的點走過一次就夠了，因為第一次重置該點的總步數一定是最小的。
3：要用優先隊列優化，先出步數最少的那個點，找到滿足條件的值就立馬break；因為優先隊列先彈出的是步數最小的那個點，后面再彈出即使滿足條件步數一定大于該點。
附上代碼：

import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; /** 寬搜，優先隊列優化*/ public class 杭電1072bfs {static int n,m,x1=0,y1=0,x2,y2,min;//行 列 初始點 結束點 結果static int d[][]= {{1,0},{0,-1},{-1,0},{0,1}};//上左下右 public static void main(String[] args) {Scanner sc =new Scanner(System.in); int T=sc.nextInt();//測試用例 while(T-->0){min=64; //看清范圍，這個是極限 n=sc.nextInt();m=sc.nextInt();//行 列int a[][]=new int[n][m]; //儲存數據 for(int i=0;i q1=new PriorityQueue<>(valuecompare);//優先隊列 q1.add(new node(x1,y1,0,6));while(!q1.isEmpty()){ node exa=q1.poll();//返回頭節點并刪除 int x=exa.x,y=exa.y;if(exa.x==x2&&exa.y==y2) {if(exa.time>0&&min>exa.value) {min=exa.value;}}else if(exa.time==0) {;}elsefor(int i=0;i<4;i ){if(x d[i][1]<0||y d[i][0]<0||x d[i][1]>=n||y d[i][0]>=m){continue;}//不越界else{if(a[x d[i][1]][y d[i][0]]==1) //普通路徑{ q1.add(new node(x d[i][1],y d[i][0],exa.value 1,exa.time-1)); } else if(a[x d[i][1]][y d[i][0]]==4)//重置區{ if(exa.time==1) {}else{q1.add(new node(x d[i][1],y d[i][0],exa.value 1,6)); a[x d[i][1]][y d[i][0]]=0;}}else if((a[x d[i][1]][y d[i][0]]==3))//結果區，讓再循環外判斷{ q1.add(new node(x d[i][1],y d[i][0],exa.value 1,exa.time-1));;} }}} }public static Comparator valuecompare =new Comparator()//接口{@Overridepublic int compare(node arg0, node arg1) { return (int)(arg0.value-arg1.value);} }; } class node//點 {int x;int y;int value;int time;public node(int x,int y,int value,int time){this.x=x;this.y=y;this.value=value;this.time=time;} }

總結

以上是生活随笔為你收集整理的杭电oj1072java实现bfs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。