Problem H
Problem Description
小边为了寻找梦寐以求的骨头误入一个迷宫,它灵敏的嗅觉告诉它,在迷宫中的某一处有一块完美的骨头.
由于迷宫会在一段时间后关闭,所以小边必须在一定时间找到那块骨头,这样才能有充足的时间来带着骨头离开.
小边在迷宫中可以从当前位置走到相邻的位置,每次移动消耗单位时间,当然,因为小边对骨头的无比执着,它偶尔会使出绝技”狗急跳墙”(一次移动两个单位位置,同样消耗单位时间).使用这个技能的时候,可以翻过一面单位厚度的墙(即第一步移动可以踩在墙上,当然也可以不踩).
hint：使用技能的时候，不用管中间那一步是否可走。
那么小边能够如愿以偿的找到骨头并离开迷宫么?
Input
多组输入
每组输入第一行是四个数m,n(0<m,n<=30),k(0<=k<=30),t(0<=t<=100),分别代表迷宫的长,宽,小边使用”狗急跳墙”的最大次数以及找到骨头的时间限制.
m=n=k=t=0代表输入结束
接下的m行每行有n个字符,‘.’代表地面,’#’代表墙,’@’代表目前小边所处的位置,’X’代表骨头所在的位置
Output
若小边能在规定时间内找到骨头,则输出Yes,否则输出No.
每个输出占一行.
Sample Input
3 3 1 2
@##
#.#
#X#
4 4 1 3
@.#.
#.##
####
##X.
0 0 0 0
Sample Output
Yes
No
这题把我搞死了。其实直接大力搜就好了，唯一要注意的地方就是：当前走到的位置，如果剩下的使用技能的次数大于曾经走到这里的次数，那么更新。当然，这里没走到过，也需要更新。这样，更新次数就不超过30*30*30次（当然事实上远小于这个数量)
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define REP(i,n) for(int i(0); i < (n); ++i)
6 #define rep(i,a,b) for(int i(a); i <= (b); ++i)
7 #define dec(i,a,b) for(int i(a); i >= (b); --i)
8 #define for_edge(i,x) for(int i = H[x]; i; i = X[i])
9
10
11 const int N =
100000 +
10;
12 const int M =
10000 +
10;
13 const int Q =
1000 +
10;
14 const int A =
100 +
1;
15
16 const int dx[] = {
0,
1,
0, -
1};
17 const int dy[] = {
1,
0, -
1,
0};
18
19 const int cx[] = {
2,
0, -
2,
0,
1, -
1,
1, -
1};
20 const int cy[] = {
0,
2,
0, -
2,
1, -
1, -
1,
1};
21
22 struct node{
23 int x, y, k, t;
24 } st, en;
25
26 char s[Q];
27 int n, m, k, t;
28 int a[A][A];
29 queue <node>
q;
30 int f[A][A];
31
32
33 bool check(
int x,
int y){
34 return (x >=
1) && (x <= m) && (y >=
1) && (y <=
n);
35 }
36
37 int main(){
38
39
40 while (~scanf(
"%d%d%d%d", &m, &n, &k, &t), n + m + k +
t){
41 memset(a,
0,
sizeof a);
42 rep(i,
1, m){
43 scanf(
"%s", s +
1);
44 rep(j,
1, n){
45 if (s[j] ==
'#'){
46 a[i][j] =
1;
47 }
48 else{
49 a[i][j] =
0;
50 if (s[j] ==
'@') st.x = i, st.y =
j;
51 if (s[j] ==
'X') en.x = i, en.y =
j;
52 }
53 }
54
55 }
56 while (!
q.empty()) q.pop();
57 st.k =
k;
58 st.t =
t;
59 q.push(st);
60 memset(f, -
1,
sizeof f);
61 f[st.x][st.y] =
k;
62 int ans =
0;
63 while (!
q.empty()){
64 node now =
q.front(); q.pop();
65 if (now.x == en.x && now.y == en.y && now.t >=
0){
66 ans =
1;
67 break;
68 }
69 REP(i,
4){
70 node nn;
71 nn.x = now.x +
dx[i];
72 nn.y = now.y +
dy[i];
73 if (check(nn.x, nn.y) && f[nn.x][nn.y] < now.k && !
a[nn.x][nn.y]){
74 nn.k =
now.k;
75 nn.t = now.t -
1;
76 if (nn.t >=
0){
77 q.push(nn);
78 f[nn.x][nn.y] =
nn.k;
79 }
80 }
81 }
82 if (now.k >
0){
83 REP(i,
8){
84 node nn;
85 nn.x = now.x +
cx[i];
86 nn.y = now.y +
cy[i];
87 if (check(nn.x, nn.y) && f[nn.x][nn.y] < now.k -
1 && !
a[nn.x][nn.y]){
88 nn.k = now.k -
1;
89 nn.t = now.t -
1;
90 if (nn.t >=
0){
91 q.push(nn);
92 f[nn.x][nn.y] =
nn.k;
93 }
94 }
95 }
96 }
97 }
98 if (ans) puts(
"Yes");
else puts(
"No");
99 }
100 return 0;
101
102 }
转载于:https://www.cnblogs.com/cxhscst2/p/6379226.html
