題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1253

Problem Description Ignatius被魔王抓走了,有一天魔王出差去了,這可是Ignatius逃亡的好機會.

魔王住在一個城堡里,城堡是一個A*B*C的立方體,可以被表示成A個B*C的矩陣,剛開始Ignatius被關(guān)在(0,0,0)的位置,離開城堡的門在(A-1,B-1,C-1)的位置,現(xiàn)在知道魔王將在T分鐘后回到城堡,Ignatius每分鐘能從一個坐標(biāo)走到相鄰的六個坐標(biāo)中的其中一個.現(xiàn)在給你城堡的地圖,請你計算出Ignatius能否在魔王回來前離開城堡(只要走到出口就算離開城堡,如果走到出口的時候魔王剛好回來也算逃亡成功),如果可以請輸出需要多少分鐘才能離開,如果不能則輸出-1.



Input 輸入數(shù)據(jù)的第一行是一個正整數(shù)K,表明測試數(shù)據(jù)的數(shù)量.每組測試數(shù)據(jù)的第一行是四個正整數(shù)A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它們分別代表城堡的大小和魔王回來的時間.然后是A塊輸入數(shù)據(jù)(先是第0塊,然后是第1塊,第2塊......),每塊輸入數(shù)據(jù)有B行,每行有C個正整數(shù),代表迷宮的布局,其中0代表路,1代表墻.(如果對輸入描述不清楚,可以參考Sample Input中的迷宮描述,它表示的就是上圖中的迷宮)

特別注意:本題的測試數(shù)據(jù)非常大,請使用scanf輸入,我不能保證使用cin能不超時.在本OJ上請使用Visual C++提交.

Output 對于每組測試數(shù)據(jù),如果Ignatius能夠在魔王回來前離開城堡,那么請輸出他最少需要多少分鐘,否則輸出-1.

Sample Input 1 3 3 4 20 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0
Sample Output 11

思路：以前做的地圖都是二維的，這是我的第一個三維的地圖，剛開始沒想到怎么定義方向合適，但還是想到方法了。

方向可以這樣定義：dir[6][3]={{0,1,0},{0,-1,0},{0,0,1},{0,0,-1},{1,0,0},{-1,0,0}}; 用二維數(shù)組，簡單粗暴。

方法和一般的廣搜一樣，看代碼：

#include<cstring> #include<iostream> #include<cmath> #include<queue>using namespace std;int dir[6][3]={{0,1,0},{0,-1,0},{0,0,1},{0,0,-1},{1,0,0},{-1,0,0}};/*這里用二維數(shù)組表示更方便些*/ int map[51][51][51]; bool vis[51][51][51];//標(biāo)記數(shù)組 int x,y,z;struct node{int x;int y;int z;int steps; };bool isGo(int a, int b, int c){//判斷當(dāng)前路徑是否可走 if(a>=0 && a<=x-1 &&b>=0 &&b<=y-1 &&c>=0 &&c<=z-1&& map[a][b][c]==0)return true;//沒越界而且當(dāng)前點有路可走 return false; }int bfs(int steps){node st,ed;queue<node> q;st.x=0;st.y=0;st.z=0;st.steps=0;q.push(st);memset(vis,false,sizeof(vis));vis[st.x][st.y][st.z]=true;while(!q.empty()){st=q.front();q.pop();if(st.steps>steps) return -1;if(st.x == x-1 &&st.y == y-1 &&st.z == z-1 &&st.steps<=steps) return st.steps;for(int i=0; i<6; ++i){ed.x=st.x+dir[i][0];ed.y=st.y+dir[i][1];ed.z=st.z+dir[i][2];if(isGo(ed.x, ed.y, ed.z) && !vis[ed.x][ed.y][ed.z]){vis[ed.x][ed.y][ed.z]=true;ed.steps=st.steps+1;if(abs(ed.x-x+1)+abs(ed.y-y+1)+abs(ed.z-z+1)+ed.steps>steps) continue;//判斷當(dāng)前路徑時候最終可以到達終點，剪枝 q.push(ed);}}}return -1;//所有點都走過但沒能到達 }int main(){int t;scanf("%d",&t);while(t--){int steps;scanf("%d%d%d%d", &x, &y, &z, &steps);for(int i=0; i<x; ++i){for(int j=0; j<y; ++j){for(int k=0; k<z; ++k)scanf("%d", &map[i][j][k]);}}int ans=bfs(steps);printf("%d\n", ans); }return 0; }

總結(jié)

以上是生活随笔為你收集整理的HD 1253 胜利大逃亡(bfs)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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