轉載請注明出處：優 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
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
