转载请注明出处：優 YoU http://user.qzone.qq.com/289065406/blog/1303446571
题目大意：
给出一三维空间的地牢
,
要求求出由字符
'S'
到字符
'E'
的最短路径
移动方向可以是上，下，左，右，前，后，六个方向
每移动一次就耗费一分钟，要求输出最快的走出时间。
不同
L
层的地图，相同
RC
坐标处是连通的
解题思路：
我越看这题就越觉得是 XX 地下城 = =
水题一道，求最短路问题，直接 BFS 得了
开三维数组，每次搜索方向由二维的 4 个方向增加到 6 个，但是方法还是那个方法
没难度
注意若果三维数组恰好开到极限的 30*30*30 是会 RE 的，别替人家电脑省空间，想 AC 就开大点。
值得一提的是。。。这题竟然被那篇经典的 POJ 分类 文章归纳到 DFS 。。。网上发现几个同学还在郁闷地 DFS 。。。。
这里就提示一下大家，凡是看到求最短路，用 DFS 一定很难做出来，一定要 BFS
1
//
Memory Time
2
//
784K 32MS
3
4
#include
<
iostream
>
5
using
namespace
std;
6
7
typedef
class
8
{
9
public
:
10
int
l,r,c;
11
int
depth;
//
树深（分钟）
12
}SE;
13
14
SE s,e;
15
bool
maze[
40
][
40
][
40
];
16
int
shortminute;
17
18
bool
BFS(
int
k,
int
i,
int
j)
19
{
20
bool
vist[
40
][
40
][
40
]
=
{
false
};
21
22
SE queue[
30000
];
23
int
head,tail;
24
queue[head
=
0
].l
=
k;
25
queue[tail
=
0
].r
=
i;
26
queue[
0
].c
=
j;
27
queue[tail
++
].depth
=
1
;
28
29
vist[k][i][j]
=
true
;
30
31
while
(head
<
tail)
32
{
33
SE x
=
queue[head
++
];
34
35
if
(x.l
==
e.l
&&
x.r
==
e.r
&&
x.c
==
e.c)
36
{
37
shortminute
=
x.depth;
38
return
true
;
39
}
40
41
if
(maze[x.l][x.r][x.c
-
1
]
&&
!
vist[x.l][x.r][x.c
-
1
])
//
West
42
{
43
vist[x.l][x.r][x.c
-
1
]
=
true
;
44
queue[tail].l
=
x.l;
45
queue[tail].r
=
x.r;
46
queue[tail].c
=
x.c
-
1
;
47
queue[tail
++
].depth
=
x.depth
+
1
;
48
}
49
if
(maze[x.l][x.r
-
1
][x.c]
&&
!
vist[x.l][x.r
-
1
][x.c])
//
North
50
{
51
vist[x.l][x.r
-
1
][x.c]
=
true
;
52
queue[tail].l
=
x.l;
53
queue[tail].r
=
x.r
-
1
;
54
queue[tail].c
=
x.c;
55
queue[tail
++
].depth
=
x.depth
+
1
;
56
}
57
if
(maze[x.l][x.r][x.c
+
1
]
&&
!
vist[x.l][x.r][x.c
+
1
])
//
East
58
{
59
vist[x.l][x.r][x.c
+
1
]
=
true
;
60
queue[tail].l
=
x.l;
61
queue[tail].r
=
x.r;
62
queue[tail].c
=
x.c
+
1
;
63
queue[tail
++
].depth
=
x.depth
+
1
;
64
}
65
if
(maze[x.l][x.r
+
1
][x.c]
&&
!
vist[x.l][x.r
+
1
][x.c])
//
South
66
{
67
vist[x.l][x.r
+
1
][x.c]
=
true
;
68
queue[tail].l
=
x.l;
69
queue[tail].r
=
x.r
+
1
;
70
queue[tail].c
=
x.c;
71
queue[tail
++
].depth
=
x.depth
+
1
;
72
}
73
if
(maze[x.l
-
1
][x.r][x.c]
&&
!
vist[x.l
-
1
][x.r][x.c])
//
Up
74
{
75
vist[x.l
-
1
][x.r][x.c]
=
true
;
76
queue[tail].l
=
x.l
-
1
;
77
queue[tail].r
=
x.r;
78
queue[tail].c
=
x.c;
79
queue[tail
++
].depth
=
x.depth
+
1
;
80
}
81
if
(maze[x.l
+
1
][x.r][x.c]
&&
!
vist[x.l
+
1
][x.r][x.c])
//
Down
82
{
83
vist[x.l
+
1
][x.r][x.c]
=
true
;
84
queue[tail].l
=
x.l
+
1
;
85
queue[tail].r
=
x.r;
86
queue[tail].c
=
x.c;
87
queue[tail
++
].depth
=
x.depth
+
1
;
88
}
89
}
90
return
false
;
91
}
92
93
int
main(
int
i,
int
j,
int
k)
94
{
95
int
L,R,C;
96
while
(cin
>>
L
>>
R
>>
C)
97
{
98
if
(
!
L
&&
!
R
&&
!
C)
99
break
;
100
101
/*
Initial
*/
102
103
memset(maze,
false
,
sizeof
(maze));
104
105
/*
Structure the Maze
*/
106
107
for
(k
=
1
;k
<=
L;k
++
)
108
for
(i
=
1
;i
<=
R;i
++
)
109
for
(j
=
1
;j
<=
C;j
++
)
110
{
111
char
temp;
112
cin
>>
temp;
113
if
(temp
==
'
.
'
)
114
maze[k][i][j]
=
true
;
115
if
(temp
==
'
S
'
)
116
{
117
maze[k][i][j]
=
true
;
118
s.l
=
k;
119
s.r
=
i;
120
s.c
=
j;
121
}
122
if
(temp
==
'
E
'
)
123
{
124
maze[k][i][j]
=
true
;
125
e.l
=
k;
126
e.r
=
i;
127
e.c
=
j;
128
}
129
}
130
131
/*
Search the min Minute
*/
132
133
if
(BFS(s.l,s.r,s.c))
134
cout
<<
"
Escaped in
"
<<
shortminute
-
1
<<
"
minute(s).
"
<<
endl;
135
else
136
cout
<<
"
Trapped!
"
<<
endl;
137
138
}
139
return
0
;
140
}
