An escape
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 227 Accepted Submission(s): 56
Problem Description
You are now in a maze. You mark all the blocks you've visited by '@',
so when you see a wall '#' or a visited block '@' in front of you, you
will make a right turn. Otherwise, that means you don't have a wall or a
visited block in front, you'll go forward. When you reach the door 'D', congratulations!
####
#Y@#
##D#
####
Look at the maze above, you are now in 'Y', facing left, and seeing a wall in
front of you. You turn right, a wall again; turn right again, visited block;
turn right once again, still a wall. After three continuous turnings, you realize
the rest time of your life will be making turnings.
Input
The first line is T(T<=20), then T cases follow.
Each case has two numbers n and m(4<=n,m <= 20), the boundary of the maze will
always be '#', in the maze, there will
be exactly one 'Y', one 'D'. Normal blocks are marked with '.'.
At first you are facing left.
Output
"YES" if you can go out of the maze(reach 'D'). "NO" otherwise.
Sample Input
2
4 4
####
#.Y#
##D#
####
4 4
####
#.Y#
#D##
####
Sample Output
NO
YES
Author
MadFroG
自己寫的超長代碼如下：
1
#include<iostream>
2#include<stdio.h>
3using namespace std;
4char a[21][21];
5void c(int x,int y,int z)//z表示轉的方向 1
6
{
7
int p=0;
8 if(z==1)
9
{
10 if(a[x][y-1]=='D')
11 {
12 printf("YES\n");
13 p++;
14
}
15
16 else if(a[x][y-1]=='.')
17 {
18 a[x][y]='@';
19 p++;
20 z=1;
21 c(x,y-1,z);
22 }
23 else if(a[x-1][y]=='D')
24 { printf("YES\n");
25 p++;}
26 else if(a[x-1][y]=='.')
27 {
28 a[x][y]='@';
29 z=2;
30 p++;
31 c(x-1,y,z);
32 }
33 else if(a[x][y+1]=='D')
34 { printf("YES\n");
35 p++;}
36 else if(a[x][y+1]=='.')
37 {
38 a[x][y]='@';
39 z=3;
40 p++;
41 c(x,y+1,z);
42 }
43 else if(a[x+1][y]=='D')
44 { printf("YES\n");
45 p++;}
46 else if(a[x+1][y]=='.')
47 {
48 a[x][y]='@';
49 z=3;
50 p++;
51 c(x+1,y,z);
52 }
53 }
54 else if(z==2)
55 {
56 if(a[x-1][y]=='D')
57 { printf("YES\n");
58 p++;}
59 else if(a[x-1][y]=='.')
60 {
61 a[x][y]='@';
62 z=2;
63 p++;
64 c(x-1,y,z);
65 }
66 else if(a[x][y+1]=='D')
67 { printf("YES\n");
68 p++;}
69 else if(a[x][y+1]=='.')
70 {
71 a[x][y]='@';
72 z=3;
73 p++;
74 c(x,y+1,z);
75 }
76 else if(a[x+1][y]=='D')
77 { printf("YES\n");
78 p++;}
79 else if(a[x+1][y]=='.')
80 {
81 a[x][y]='@';
82 z=3;
83 p++;
84 c(x+1,y,z);
85 }
86 else if(a[x][y-1]=='D')
87 { printf("YES\n");
88 p++;}
89 else if(a[x][y-1]=='.')
90 {
91 a[x][y]='@';
92 p++;
93 z=1;
94 c(x,y-1,z);
95 }
96 }
97 else if(z==3)
98 {
99 if(a[x][y+1]=='D')
100 { printf("YES\n");
101 p++;}
102 else if(a[x][y+1]=='.')
103 {
104 a[x][y]='@';
105 z=3;
106 p++;
107 c(x,y+1,z);
108 }
109 else if(a[x+1][y]=='D')
110 { printf("YES\n");
111 p++;}
112 else if(a[x+1][y]=='.')
113 {
114 a[x][y]='@';
115 z=3;
116 p++;
117 c(x+1,y,z);
118 }
119 else if(a[x][y-1]=='D')
120 { printf("YES\n");
121 p++;}
122 else if(a[x][y-1]=='.')
123 {
124 a[x][y]='@';
125 p++;
126 z=1;
127 c(x,y-1,z);
128 }
129 else if(a[x-1][y]=='D')
130 { printf("YES\n");
131 p++;}
132 else if(a[x-1][y]=='.')
133 {
134 a[x][y]='@';
135 z=2;
136 p++;
137 c(x-1,y,z);
138 }
139 }
140 else if(z==4)
141 {
142 if(a[x+1][y]=='D')
143 { printf("YES\n");
144 p++;}
145 else if(a[x+1][y]=='.')
146 {
147 a[x][y]='@';
148 z=3;
149 p++;
150 c(x+1,y,z);
151 }
152 else if(a[x][y-1]=='D')
153 { printf("YES\n");
154 p++;}
155 else if(a[x][y-1]=='.')
156 {
157 a[x][y]='@';
158 p++;
159 z=1;
160 c(x,y-1,z);
161 }
162 else if(a[x-1][y]=='D')
163 { printf("YES\n");
164 p++;}
165 else if(a[x-1][y]=='.')
166 {
167 a[x][y]='@';
168 z=2;
169 p++;
170 c(x-1,y,z);
171 }
172 else if(a[x][y+1]=='D')
173 { printf("YES\n");
174 p++;}
175 else if(a[x][y+1]=='.')
176 {
177 a[x][y]='@';
178 z=3;
179 p++;
180 c(x,y+1,z);
181 }
182 }
183 if(p==0)
184 printf("NO\n");
185
}
186int main()
187 {
188 int T;
189 int n,m;
190 scanf("%d",&T);
191 for(int i=1;i<=T;i++)
192 {
193 scanf("%d%d",&n,&m);
194 for(int j=1;j<=n;j++){
195
196 for(int k=1;k<=m;k++)
197 {
198 scanf("%c",&a[j][k]);
199
200 } getchar();
201 }
202 for(int j=1;j<=n;j++)
203 for(int k=1;k<=m;k++)
204 {
205 if(a[j][k]=='Y')
206 {
207 c(j,k,1);
208 }
209 }
210 }
211 return 0;
212 }
213
深搜的代碼
1#include<iostream>
2#include<stdio.h>
3using namespace std;
4char a[21][21];
5int aa[][4]={{0,1,2,3},{1,2,3,0},{2,3,0,1},{3,0,1,2}};
6int kk=0,flag=0;
7int x_end,y_end;
8void dfs(int x,int y)
9{
10
11 int k=kk;
12 if(x==x_end&&y==y_end)//不能用=='D' 因為在上一層已經將 D的值改變
13 {
14
15 flag=1;
16 return ;
17 }
18 for(int i=0;i<4&&!flag;++i)
19 {
20 if(aa[k][i]==0&&a[x][y-1]!='#')
21 {
22 a[x][y-1]='#';
23 kk=0;dfs(x,y-1);break;//不能回溯的 因為只有一條路可走
24 }
25 if(aa[k][i]==1&&a[x-1][y]!='#')
26 {
27 a[x-1][y]='#';kk=1;dfs(x-1,y);break;
28 }
29 if(aa[k][i]==2&&a[x][y+1]!='#')
30 {
31 a[x][y+1]='#';kk=2;dfs(x,y+1);break;
32 }
33 if(aa[k][i]==3&&a[x+1][y]!='#')
34 {
35 a[x+1][y]='#';kk=3;dfs(x+1,y);break;
36 }
37 }
38}
39int main()
40 {
41 //freopen("in.txt","r",stdin);
42 int T;
43 int n,m;
44 scanf("%d",&T);
45 for(int i=1;i<=T;i++)
46 {
47 kk=0;
48 flag=0;//在循環的開始對kk和flag進行清零
49 scanf("%d%d",&n,&m);
50 getchar();
51 for(int j=1;j<=n;j++)
52 {
53 for(int k=1;k<=m;k++)
54 {
55 scanf("%c",&a[j][k]);
56 if(a[j][k]=='D')
57 {
58 x_end=j;
59 y_end=k;
60 }
61 }
62 getchar();
63 }
64
65 for(int j=1;j<=n;j++)
66 for(int k=1;k<=m;k++)
67 {
68 if(a[j][k]=='Y')
69 {
70 a[j][k]='#';
71 dfs(j,k);
72 }
73 }
74 if(flag==1)
75 printf("YES\n");
76 else
77 printf("NO\n");
78
79 }
80 return 0;
81 }
82