1248：Dungeon Master

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 8637 ??? 通過數(shù): 3432

【題目描述】

這題是一個(gè)三維的迷宮題目，其中用‘.’表示空地，‘#’表示障礙物，‘S’表示起點(diǎn)，‘E’表示終點(diǎn)，求從起點(diǎn)到終點(diǎn)的最小移動(dòng)次數(shù)，解法和二維的類似，只是在行動(dòng)時(shí)除了東南西北移動(dòng)外還多了上下。可以上下左右前后移動(dòng)，每次都只能移到相鄰的空位，每次需要花費(fèi)一分鐘，求從起點(diǎn)到終點(diǎn)最少要多久。

【輸入】

多組測(cè)試數(shù)據(jù)。

一組測(cè)試測(cè)試數(shù)據(jù)表示一個(gè)三維迷宮：

前三個(gè)數(shù)，分別表示層數(shù)、一個(gè)面的長(zhǎng)和寬，后面是每層的平面圖。前三個(gè)數(shù)據(jù)為三個(gè)零表示結(jié)束。

【輸出】

最小移動(dòng)次數(shù)。

【輸入樣例】

3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0

【輸出樣例】

Escaped in 11 minute(s). Trapped!

【提示】

對(duì)于題目給出數(shù)據(jù)的含義就是輸入l，r，c，分別代表迷宮有l(wèi)層，每層長(zhǎng)寬分別是c，r。對(duì)于數(shù)據(jù)以可以這樣移動(dòng):

?(1,1,1)->(1,1,2)->(1,1,3)->(1,1,4)->(1,1,5)->(1,2,5)->

?(1,3,5)->(1,3,4)->(1,4,4)->(2,4,4)->(2,4,5)->(3,4,,5)

?共11步就可以到達(dá)終點(diǎn) 對(duì)于數(shù)據(jù)二明顯不能到達(dá)，則輸出Trapped！

?這題用BFS解，每次去隊(duì)首元素，如果是終點(diǎn)則輸出結(jié)果移動(dòng)的次數(shù)，否則，從該點(diǎn)開始分別向東南西北上下移動(dòng)（如果可以走的話）并繼續(xù)搜，如果到隊(duì)列為空還沒搜到解法，則說明無解。

【分析】

? ? ? ? 這題是一個(gè)三維的迷宮題目，很顯然，地圖和訪問數(shù)組都是三維的。方向數(shù)組六個(gè)方向，除了東南西北，還有上和下。

【參考代碼】

#include <iostream> #include <cstdio> #include <cstring> #include <queue>using namespace std;const int N=110; struct node {int z;int x;int y;int step; };int l,n,m; int vis[N][N][N]; //訪問數(shù)組 char map[N][N][N]; //地圖數(shù)組 int u[][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; //方向數(shù)組 void bfs(node s,node e) {queue <node> q;bool flag=true;q.push(s);while(!q.empty()){node a=q.front();for(int i=0;i<6;i++){node nw;nw.z =a.z+u[i][0];nw.x =a.x+u[i][1];nw.y =a.y+u[i][2];nw.step =a.step +1;if(nw.z >=0 && nw.z <l && nw.x >=0 && nw.x <n && nw.y >=0 && nw.y <m && (!vis[nw.z][nw.x][nw.y]) && map[nw.z][nw.x][nw.y]=='.'){q.push(nw);vis[nw.z][nw.x][nw.y]=1;if(nw.z==e.z && nw.x==e.x && nw.y==e.y){printf("Escaped in %d minute(s).\n",a.step+1);flag=false;return;}}}q.pop();}if(flag)printf("Trapped!\n"); } int main() {while(scanf("%d%d%d",&l,&n,&m)==3,l+n+m){node s,e;memset(vis,0,sizeof(vis));for(int k=0;k<l;k++)for(int i=0;i<n;i++)scanf("%s",map[k][i]);for(int k=0;k<l;k++){for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(map[k][i][j]=='S'){s.z=k;s.x=i;s.y=j;s.step=0;}if(map[k][i][j]=='E'){e.z=k;e.x=i;e.y=j;map[k][i][j]='.';}}}}bfs(s,e);}return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1248

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1248：Dungeon Master）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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