題目大意：你如今處在一個3D空間中，每單位時間可以東、西、南、北、上、下六個方向走，要求在最短的時間內到達終點。
典型的BFS，116行的代碼一次AC也算是增加信心了。
1 #include<stdio.h>
2 const long maxn=37,maxlen=maxn*maxn*maxn,INF=200007;
3 const long xd[]={-1,1,0,0,0,0},yd[]={0,0,-1,0,1,0},zd[]={0,0,0,1,0,-1};
4 typedef struct
5 {
6 long x,y,z;
7 }point;
8 typedef struct
9 {
10 long front,rear,count;
11 point item[maxlen];
12 }queue;
13 void clear(queue &q)
14 {
15 q.count=0;
16 q.front=0;
17 q.rear=-1;
18 }
19 bool empty(queue &q)
20 {
21 return (q.count==0);
22 }
23 void push(queue &q,point x)
24 {
25 q.rear++;
26 q.item[q.rear]=x;
27 q.count++;
28 }
29 void pop(queue &q,point &x)
30 {
31 x=q.item[q.front];
32 q.front++;
33 q.count--;
34 }
35 // Queue
36
37 int main()
38 {
39 /*
40 freopen("data.in","r",stdin);
41 freopen("data.out","w",stdout);
42 //*/
43 long l,r,c;
44 long g[maxn][maxn][maxn],d[maxn][maxn][maxn];
45 bool used[maxn][maxn][maxn];
46 while(scanf("%ld%ld%ld",&l,&r,&c)==3)
47 {
48 if(l==0||r==0||c==0) break;
49 getchar();
50 point begin,end;
51 for(long k=1;k<=l;k++)
52 {
53 for(long i=1;i<=r;i++)
54 {
55 for(long j=1;j<=c;j++)
56 {
57 char tmp;
58 scanf("%c",&tmp);
59 if(tmp=='S')
60 {
61 begin.x=k;begin.y=i;begin.z=j;
62 g[k][i][j]=7;
63 }
64 else if(tmp=='E')
65 {
66 end.x=k;end.y=i;end.z=j;
67 g[k][i][j]=-1;
68 }
69 else if(tmp=='.')
70 g[k][i][j]=1;
71 else if(tmp=='#')
72 g[k][i][j]=0;
73 }
74 getchar();
75 }
76 getchar();
77 }
78 // Input
79
80 for(long i=1;i<=l;i++)
81 for(long j=1;j<=r;j++)
82 for(long k=1;k<=c;k++)
83 {
84 d[i][j][k]=INF;
85 used[i][j][k]=false;
86 }
87 d[begin.x][begin.y][begin.z]=0;
88 // Clear
89
90 queue q;clear(q);
91 used[begin.x][begin.y][begin.z]=true;
92 push(q,begin);
93 while(!empty(q))
94 {
95 point tmp,newp;
96 pop(q,tmp);
97 long xx=tmp.x,yy=tmp.y,zz=tmp.z;
98 for(long k=0;k<6;k++)
99 {
100 long tx=xx+xd[k],ty=yy+yd[k],tz=zz+zd[k];
101 if(tx>=1&&tx<=l&&ty>=1&&ty<=r&&tz>=1&&tz<=c&&g[tx][ty][tz]&&!used[tx][ty][tz])
102 {
103 d[tx][ty][tz]=d[xx][yy][zz]+1;
104 used[tx][ty][tz]=true;
105 newp.x=tx;newp.y=ty;newp.z=tz;
106 push(q,newp);
107 }
108 }
109 }
110 if(d[end.x][end.y][end.z]<INF)
111 printf("Escaped in %ld minute(s).\n",d[end.x][end.y][end.z]);
112 else printf("Trapped!\n");
113 }
114 return 0;
115 }
116
posted on 2010-01-23 11:29
lee1r 閱讀(447)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索