魔戒 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description

蓝色空间号和万有引力号进入了四维水洼，发现了四维物体–魔戒。 这里我们把飞船和魔戒都抽象为四维空间中的一个点，分别标为 “S” 和 “E”。空间中可能存在障碍物，标为 “#”，其他为可以通过的位置。 现在他们想要尽快到达魔戒进行探索，你能帮他们算出最小时间是最少吗？我们认为飞船每秒只能沿某个坐标轴方向移动一个单位，且不能越出四维空间。 Input

输入数据有多组（数据组数不超过 30），到 EOF 结束。 每组输入 4 个数 x, y, z, w 代表四维空间的尺寸（1 <= x, y, z, w <= 30）。 接下来的空间地图输入按照 x, y, z, w 轴的顺序依次给出，你只要按照下面的坐标关系循环读入即可。 for 0, x-1 for 0, y-1 for 0, z-1 for 0, w-1 保证 “S” 和 “E” 唯一。 Output

对于每组数据，输出一行，到达魔戒所需的最短时间。 如果无法到达，输出 “WTF”（不包括引号）。 Example Input

2 2 2 2 .. .S ..

.

.

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

.

#

E. .#

.

.. Example Output

1 3 Hint

Author

「“师创杯”山东理工大学第九届ACM程序设计竞赛 正式赛」bLue

#include<bits/stdc++.h> using namespace std; const int MAX = 30; char map1[MAX][MAX][MAX][MAX];//记录图的标记 bool visit[MAX][MAX][MAX][MAX];//记录点是否被访问过 int dirt[8][4] = {{1,0,0,0},{-1,0,0,0}, {0,1,0,0},{0,-1,0,0},{0,0,1,0}, {0,0,-1,0},{0,0,0,1},{0,0,0,-1} };//行走的方向 int x,y,z,w;//每维空间的大小 struct info { int x,y,z,w; int step; }s; bool judge(info each)//判断访问的点是否合法 { if(each.x>=0&&each.x<x &&each.y>=0&&each.y<y &&each.z>=0&&each.z<z &&each.w>=0&&each.w<w &&map1[each.x][each.y][each.z][each.w]!='#') { return true; } else return false; } int bfs() { queue<info> que; que.push(s); memset(visit,false,sizeof(visit)); visit[s.x][s.y][s.z][s.w] = true; while(!que.empty()) { info f = que.front(); que.pop(); if(map1[f.x][f.y][f.z][f.w]=='E') return f.step; for(int i = 0;i<8;i++) { info next = f; next.x += dirt[i][0]; next.y += dirt[i][1]; next.z += dirt[i][2]; next.w += dirt[i][3]; if(judge(next)&&!visit[next.x][next.y][next.z][next.w]) { next.step++; que.push(next); visit[next.x][next.y][next.z][next.w] = true; } } } return -1; } int main() { while(cin>>x>>y>>z>>w) { for(int i = 0;i<x;i++) { for(int j = 0;j<y;j++) { for(int k = 0;k<z;k++) { scanf("%s",map1[i][j][k]); for(int l = 0;l<w;l++) { if(map1[i][j][k][l]=='S') { s = (info){i,j,k,l,0}; } } } } } int ans = bfs(); if(ans != - 1) { cout<<ans<<endl; } else { cout<<"WTF"<<endl; } } return 0; }