建设网站科目,手机怎么编辑网页,网站设计动画,商务网站开发实验报告Description 蓝色空间号和万有引力号进入了四维水洼#xff0c;发现了四维物体--魔戒。 这里我们把飞船和魔戒都抽象为四维空间中的一个点#xff0c;分别标为 S 和 E。空间中可能存在障碍物#xff0c;标为 ##xff0c;其他为可以通… 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不包括引号。 Sample Input 2 2 2 2
..
.S
..
#.
#.
.E
.#
..
2 2 2 2
..
.S
#.
##
E.
.#
#.
..Sample Output 1
3题解其实四维空间博主也不太懂这道题其实题意很简单求s-E的最短路直接4维数组bfs搜一下就好 1 #includecstdio2 #includecstring3 #includestack4 #includequeue5 #includealgorithm6 #includemap7 #includevector8 #define PI acos(-1.0)9 using namespace std;
10 #define Inf 0x3f3f3f3f
11 typedef long long ll;
12 int m,n,x,y,flag0;
13 char str[45][45][45][45];
14 int visit[50][50][50][50];
15 int dis[500][500];
16 int di[8][4] {{0,0,0,1},{0,0,0,-1},{0,0,1,0},{0,0,-1,0},{0,1,0,0},{0,-1,0,0},{1,0,0,0},{-1,0,0,0}};
17 mapll,ll::iterator it;
18 struct node
19 {
20 int x,y,z,w,step;
21 } ;
22 int bfs(int sx,int sy,int sz,int sw)
23 {
24 queuenodepp;
25 node s,q;
26 s.xsx;
27 s.ysy;
28 s.zsz;
29 s.wsw;
30 s.step0;
31 pp.push(s);
32 memset(visit,0,sizeof(visit));
33 visit[s.x][s.y][s.z][s.w]1;
34 while(!pp.empty())
35 {
36 spp.front();
37 if(str[s.x][s.y][s.z][s.w]E)
38 {
39 flag0;
40 return s.step;
41 }
42 pp.pop();
43 for(int i0; i8; i)
44 {
45 q.xs.xdi[i][0];
46 q.ys.ydi[i][1];
47 q.zs.zdi[i][2];
48 q.ws.wdi[i][3];
49 q.steps.step;
50 if(q.x0q.xmq.y0q.ynq.z0q.zxq.w0q.wy!visit[q.x][q.y][q.z][q.w]str[q.x][q.y][q.z][q.w]!#)
51 {
52 q.step;
53 visit[q.x][q.y][q.z][q.w]1;
54 pp.push(q);
55 }
56 }
57 }
58 }
59 int main()
60 {
61 int z,w,sx,sy,sz,sw,i,j,ans;
62 while(scanf(%d%d%d%d,m,n,x,y)!-1)
63 {
64 flag1;
65 for(i0; im; i)
66 for(j0; jn; j)
67 for(z0; zx; z)
68 for(w0; wy; w)
69 {
70 scanf( %c,str[i][j][z][w]);
71 if(str[i][j][z][w]S)
72 {
73 sxi,syj,szz,sww;
74 }
75
76 }
77 ansbfs(sx,sy,sz,sw);
78 if(flag)
79 puts(WTF);
80 else
81 printf(%d\n,ans);
82 }
83 return 0;
84 } View Code 题意很简单从s-E的最短路4维数组bfs搜索一下就哦了bfs裸题 转载于:https://www.cnblogs.com/moomcake/p/9351174.html
