Description

藍色空間號和萬有引力號進入了四維水洼，發(fā)現(xiàn)了四維物體--魔戒。

這里我們把飛船和魔戒都抽象為四維空間中的一個點，分別標為 "S" 和 "E"。空間中可能存在障礙物，標為 "#"，其他為可以通過的位置。

現(xiàn)在他們想要盡快到達魔戒進行探索，你能幫他們算出最小時間是最少嗎？我們認為飛船每秒只能沿某個坐標軸方向移動一個單位，且不能越出四維空間。

Input

輸入數(shù)據(jù)有多組（數(shù)據(jù)組數(shù)不超過 30），到 EOF 結束。

每組輸入 4 個數(shù) x, y, z, w 代表四維空間的尺寸（1 <= x, y, z, w <= 30）。

接下來的空間地圖輸入按照 x, y, z, w 軸的順序依次給出，你只要按照下面的坐標關系循環(huán)讀入即可。

for 0, x-1

? ??for 0, y-1

? ? ? ??for 0, z-1

? ? ? ? ? ??for 0, w-1

保證 "S" 和 "E" 唯一。

Output

對于每組數(shù)據(jù)，輸出一行，到達魔戒所需的最短時間。

如果無法到達，輸出 "WTF"（不包括引號）。

Sample Input

2 2 2 2 .. .S .. #. #. .E .# .. 2 2 2 2 .. .S #. ## E. .# #. ..

Sample Output

1 3

解題思路：開始看到這個題腦子有點發(fā)懵，題目提到了四維空間看了看所給的樣例我還真是不知道這個四維空間是怎么組成的，好在題目有說明，我知道這是一道搜索的題，于是在看不懂題目下硬生生地照著BFS模板一頓狂敲，ac了這道題，
裸裸的模板題！！！

#include <stdio.h> #include <queue> #include <string.h> using namespace std; int A,B,C,D; char map[55][55][55][55]; int vis[55][55][55][55]; int dirx[]= {1,-1,0,0,0,0,0,0}; int diry[]= {0,0,1,-1,0,0,0,0}; int dirz[]= {0,0,0,0,1,-1,0,0}; int dirw[]= {0,0,0,0,0,0,1,-1};///飛船只能沿著坐標軸方向移動 int aa,bb,cc,dd; struct node {int x;///記錄在四維空間中的位置int y;int z;int w;int step;///記錄飛船移動的步數(shù) }; int judge(int x,int y,int z,int w)///判斷所在的位置是否合法，既要在四維空間內(nèi)還要能走并且沒有訪問過 {if (x>=0&&x<A&&y>=0&&y<B&&z>=0&&z<C&&w>=0&&w<D){if(vis[x][y][z][w]==0&&map[x][y][z][w]!='#'){return 1;}}return 0; } int bfs(int aa,int bb,int cc,int dd) {queue<node>Q;int flag;node a;a.x=aa;a.y=bb;a.z=cc;a.w=dd;a.step=0;vis[aa][bb][cc][dd]=1;Q.push(a);flag=1;while (!Q.empty()){a=Q.front();if (map[a.x][a.y][a.z][a.w]=='E'){return a.step;}for (int i=0; i<8; i++){node b;b=a;b.x+=dirx[i];b.y+=diry[i];b.z+=dirz[i];b.w+=dirw[i];if (judge(b.x,b.y,b.z,b.w)){b.step++;vis[b.x][b.y][b.z][b.w]=1;Q.push(b);}}Q.pop();}return -100; } int main () {int ans;while(scanf ("%d%d%d%d",&A,&B,&C,&D)!=EOF){getchar();for (int i=0; i<A; i++){for (int j=0; j<B; j++){for (int k=0; k<C; k++){for(int l=0; l<D; l++){scanf ("%c",&map[i][j][k][l]);if (map[i][j][k][l]=='S'){aa=i;bb=j;cc=k;dd=l;///記錄下飛船在四維空間的起始位置 }}getchar();}}}memset(vis,0,sizeof(vis));ans=bfs(aa,bb,cc,dd);if (ans==-100){printf ("WTF\n");}else{printf("%d\n",ans);}}return 0; }

?

如果說沿一條筆直的直線行走就是在一維空間中，再轉一下彎就是在二維空間中，再有一點坡度就可以看成是在三維空間中運動，那么四維空間是什么樣呢？值得思考啊

?

轉載于:https://www.cnblogs.com/wkfvawl/p/9348011.html

總結

以上是生活随笔為你收集整理的魔戒（广搜）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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