poj3083ChildrenoftheCandyCorn（dfs+bfs)

1 #include
2 #include
3 #include
4 using namespace std;
5 int m,n;
6 int map[45][45];
7 int s[4][2]&＃61;{{-1,0},{1,0},{0,1},{0,-1}};
8 struct node
9 {
10 int x,y;
11 int num;
12 }que[20000];
13 char str[45][45];
14 int lsum&＃61;0;
15 int flag;
16 int rsum&＃61;0;
17 void bfs(int sx,int sy)
18 {
19 int i;
20 int head,tail;
21 memset(map,0,sizeof(map));
22 que[0].x&＃61;sx;
23 que[0].y&＃61;sy;
24 que[0].num&＃61;1;
25 head&＃61;0;
26 tail&＃61;1;
27 map[sx][sy]&＃61;1;
28 while(head<tail)
29 {
30 int xi;
31 int yi;
32 for(i&＃61;0;i<4;i&＃43;&＃43;)
33 {
34 xi&＃61;que[head].x&＃43;s[i][0];
35 yi&＃61;que[head].y&＃43;s[i][1];
36 if(str[xi][yi]&＃61;&＃61;&＃39;E&＃39;)
37 {
38 cout<1<<endl;
39 return ;
40 }
41 if(str[xi][yi]&＃61;&＃61;&＃39;.&＃39;&&xi>&＃61;1&&xi<&＃61;n&&yi>&＃61;1&&yi<&＃61;m&&map[xi][yi]&＃61;&＃61;0)
42 {
43 que[tail].x&＃61;xi;
44 que[tail].y&＃61;yi;
45 que[tail].num&＃61;que[head].num&＃43;1;
46 map[xi][yi]&＃61;1;
47 tail&＃43;&＃43;;
48 }
49 }
50 head&＃43;&＃43;;
51 }
52
53 }
54 void ldfs(int ax,int ay,int dec)
55 {
56 if(flag)
57 return;
58 if(str[ax][ay]&＃61;&＃61;&＃39;E&＃39;)
59 {
60 lsum&＃43;&＃43;;
61 flag&＃61;1;
62 return ;
63 }
64 if(!flag)
65 {
66 if(dec&＃61;&＃61;1)
67 {
68 if(ay&＃43;1<&＃61;m&&(str[ax][ay&＃43;1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay&＃43;1]&＃61;&＃61;&＃39;E&＃39;))
69 {
70 lsum&＃43;&＃43;;
71 ldfs(ax,ay&＃43;1,4);
72 if(flag)
73 return ;
74 }
75 if(ax&＃43;1<&＃61;n&&(str[ax&＃43;1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax&＃43;1][ay]&＃61;&＃61;&＃39;E&＃39;))
76 {
77 lsum&＃43;&＃43;;
78 ldfs(ax&＃43;1,ay,1);
79 if(flag)
80 return ;
81 }
82 if(ay-1>&＃61;1&&(str[ax][ay-1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay-1]&＃61;&＃61;&＃39;E&＃39;))
83 {
84 lsum&＃43;&＃43;;
85 ldfs(ax,ay-1,2);
86 if(flag)
87 return ;
88 }
89 if(ax-1>&＃61;1&&(str[ax-1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax-1][ay]&＃61;&＃61;&＃39;E&＃39;))
90 {
91 lsum&＃43;&＃43;;
92 ldfs(ax-1,ay,3);
93 if(flag)
94 return ;
95 }
96 }
97 else if(dec&＃61;&＃61;2)
98 {
99 if(ax&＃43;1<&＃61;n&&(str[ax&＃43;1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax&＃43;1][ay]&＃61;&＃61;&＃39;E&＃39;))
100 {
101 lsum&＃43;&＃43;;
102 ldfs(ax&＃43;1,ay,1);
103 if(flag)
104 return ;
105 }
106 if(ay-1>&＃61;1&&(str[ax][ay-1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay-1]&＃61;&＃61;&＃39;E&＃39;))
107 {
108 lsum&＃43;&＃43;;
109 ldfs(ax,ay-1,2);
110 if(flag)
111 return ;
112 }
113 if(ax-1>&＃61;1&&(str[ax-1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax-1][ay]&＃61;&＃61;&＃39;E&＃39;))
114 {
115 lsum&＃43;&＃43;;
116 ldfs(ax-1,ay,3);
117 if(flag)
118 return ;
119 }
120 if(ay&＃43;1<&＃61;m&&(str[ax][ay&＃43;1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay&＃43;1]&＃61;&＃61;&＃39;E&＃39;))
121 {
122 lsum&＃43;&＃43;;
123 ldfs(ax,ay&＃43;1,4);
124 if(flag)
125 return ;
126 }
127
128 }
129 else if(dec&＃61;&＃61;3)
130 {
131 if(ay-1>&＃61;1&&(str[ax][ay-1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay-1]&＃61;&＃61;&＃39;E&＃39;))
132 {
133 lsum&＃43;&＃43;;
134 ldfs(ax,ay-1,2);
135 if(flag)
136 return ;
137 }
138 if(ax-1>&＃61;1&&(str[ax-1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax-1][ay]&＃61;&＃61;&＃39;E&＃39;))
139 {
140 lsum&＃43;&＃43;;
141 ldfs(ax-1,ay,3);
142 if(flag)
143 return ;
144 }
145 if(ay&＃43;1<&＃61;m&&(str[ax][ay&＃43;1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay&＃43;1]&＃61;&＃61;&＃39;E&＃39;))
146 {
147 lsum&＃43;&＃43;;
148 ldfs(ax,ay&＃43;1,4);
149 if(flag)
150 return ;
151 }
152 if(ax&＃43;1<&＃61;n&&(str[ax&＃43;1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax&＃43;1][ay]&＃61;&＃61;&＃39;E&＃39;))
153 {
154 lsum&＃43;&＃43;;
155 ldfs(ax&＃43;1,ay,1);
156 if(flag)
157 return ;
158 }
159 }
160 else
161 {
162 if(ax-1>&＃61;1&&(str[ax-1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax-1][ay]&＃61;&＃61;&＃39;E&＃39;))
163 {
164 lsum&＃43;&＃43;;
165 ldfs(ax-1,ay,3);
166 if(flag)
167 return ;
168 }
169 if(ay&＃43;1<&＃61;m&&(str[ax][ay&＃43;1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay&＃43;1]&＃61;&＃61;&＃39;E&＃39;))
170 {
171 lsum&＃43;&＃43;;
172 ldfs(ax,ay&＃43;1,4);
173 if(flag)
174 return ;
175 }
176 if(ax&＃43;1<&＃61;n&&(str[ax&＃43;1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax&＃43;1][ay]&＃61;&＃61;&＃39;E&＃39;))
177 {
178 lsum&＃43;&＃43;;
179 ldfs(ax&＃43;1,ay,1);
180 if(flag)
181 return ;
182 }
183 if(ay-1>&＃61;1&&(str[ax][ay-1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay-1]&＃61;&＃61;&＃39;E&＃39;))
184 {
185 lsum&＃43;&＃43;;
186 ldfs(ax,ay-1,2);
187 if(flag)
188 return ;
189 }
190 }
191 }
192 return ;
193 }
194 void rdfs(int ax,int ay,int dec)
195 {
196 if(flag)
197 return;
198 if(str[ax][ay]&＃61;&＃61;&＃39;E&＃39;)
199 {
200 rsum&＃43;&＃43;;
201 flag&＃61;1;
202 return ;
203 }
204 if(!flag)
205 {
206 if(dec&＃61;&＃61;1)
207 {
208 if(ay-1>&＃61;1&&(str[ax][ay-1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay-1]&＃61;&＃61;&＃39;E&＃39;))
209 {
210 rsum&＃43;&＃43;;
211 rdfs(ax,ay-1,2);
212 if(flag)
213 return ;
214 }
215 if(ax&＃43;1<&＃61;n&&(str[ax&＃43;1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax&＃43;1][ay]&＃61;&＃61;&＃39;E&＃39;))
216 {
217 rsum&＃43;&＃43;;
218 rdfs(ax&＃43;1,ay,1);
219 if(flag)
220 return ;
221 }
222
223 if(ay&＃43;1<&＃61;m&&(str[ax][ay&＃43;1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay&＃43;1]&＃61;&＃61;&＃39;E&＃39;))
224 {
225 rsum&＃43;&＃43;;
226 rdfs(ax,ay&＃43;1,4);
227 if(flag)
228 return ;
229 }
230 if(ax-1>&＃61;1&&(str[ax-1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax-1][ay]&＃61;&＃61;&＃39;E&＃39;))
231 {
232 rsum&＃43;&＃43;;
233 rdfs(ax-1,ay,3);
234 if(flag)
235 return ;
236 }
237 }
238 else if(dec&＃61;&＃61;2)
239 {
240 if(ax-1>&＃61;1&&(str[ax-1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax-1][ay]&＃61;&＃61;&＃39;E&＃39;))
241 {
242 rsum&＃43;&＃43;;
243 rdfs(ax-1,ay,3);
244 if(flag)
245 return ;
246 }
247 if(ay-1>&＃61;1&&(str[ax][ay-1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay-1]&＃61;&＃61;&＃39;E&＃39;))
248 {
249 rsum&＃43;&＃43;;
250 rdfs(ax,ay-1,2);
251 if(flag)
252 return ;
253 }
254
255 if(ax&＃43;1<&＃61;n&&(str[ax&＃43;1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax&＃43;1][ay]&＃61;&＃61;&＃39;E&＃39;))
256 {
257 rsum&＃43;&＃43;;
258 rdfs(ax&＃43;1,ay,1);
259 if(flag)
260 return ;
261 }
262 if(ay&＃43;1<&＃61;m&&(str[ax][ay&＃43;1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay&＃43;1]&＃61;&＃61;&＃39;E&＃39;))
263 {
264 rsum&＃43;&＃43;;
265 rdfs(ax,ay&＃43;1,4);
266 if(flag)
267 return ;
268 }
269
270 }
271 else if(dec&＃61;&＃61;3)
272 {
273 if(ay&＃43;1<&＃61;m&&(str[ax][ay&＃43;1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay&＃43;1]&＃61;&＃61;&＃39;E&＃39;))
274 {
275 rsum&＃43;&＃43;;
276 rdfs(ax,ay&＃43;1,4);
277 if(flag)
278 return ;
279 }
280 if(ax-1>&＃61;1&&(str[ax-1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax-1][ay]&＃61;&＃61;&＃39;E&＃39;))
281 {
282 rsum&＃43;&＃43;;
283 rdfs(ax-1,ay,3);
284 if(flag)
285 return ;
286 }
287
288 if(ay-1>&＃61;1&&(str[ax][ay-1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay-1]&＃61;&＃61;&＃39;E&＃39;))
289 {
290 rsum&＃43;&＃43;;
291 rdfs(ax,ay-1,2);
292 if(flag)
293 return ;
294 }
295 if(ax&＃43;1<&＃61;n&&(str[ax&＃43;1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax&＃43;1][ay]&＃61;&＃61;&＃39;E&＃39;))
296 {
297 rsum&＃43;&＃43;;
298 rdfs(ax&＃43;1,ay,1);
299 if(flag)
300 return ;
301 }
302 }
303 else
304 {
305 if(ax&＃43;1<&＃61;n&&(str[ax&＃43;1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax&＃43;1][ay]&＃61;&＃61;&＃39;E&＃39;))
306 {
307 rsum&＃43;&＃43;;
308 rdfs(ax&＃43;1,ay,1);
309 if(flag)
310 return ;
311 }
312 if(ay&＃43;1<&＃61;m&&(str[ax][ay&＃43;1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay&＃43;1]&＃61;&＃61;&＃39;E&＃39;))
313 {
314 rsum&＃43;&＃43;;
315 rdfs(ax,ay&＃43;1,4);
316 if(flag)
317 return ;
318 }
319
320 if(ax-1>&＃61;1&&(str[ax-1][ay]&＃61;&＃61;&＃39;.&＃39;||str[ax-1][ay]&＃61;&＃61;&＃39;E&＃39;))
321 {
322 rsum&＃43;&＃43;;
323 rdfs(ax-1,ay,3);
324 if(flag)
325 return ;
326 }
327 if(ay-1>&＃61;1&&(str[ax][ay-1]&＃61;&＃61;&＃39;.&＃39;||str[ax][ay-1]&＃61;&＃61;&＃39;E&＃39;))
328 {
329 rsum&＃43;&＃43;;
330 rdfs(ax,ay-1,2);
331 if(flag)
332 return ;
333 }
334 }
335 }
336 return ;
337 }
338 int main()
339 {
340 int t;
341
342 cin>>t;
343 int sx,sy;
344 int i,j;
345 int f;
346 while(t--)
347 {
348 cin>>m>>n;
349 for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
350 {
351 for(j&＃61;1;j<&＃61;m;j&＃43;&＃43;)
352 {
353 cin>>str[i][j];
354 if(str[i][j]&＃61;&＃61;&＃39;S&＃39;)
355 {
356 sx&＃61;i;
357 sy&＃61;j;
358 }
359 }
360 }
361 if(sx&＃61;&＃61;1)
362 f&＃61;1;
363 if(sx&＃61;&＃61;n)
364 f&＃61;3;
365 if(sy&＃61;&＃61;1)
366 f&＃61;4;
367 if(sy&＃61;&＃61;m)
368 f&＃61;2;
369 flag&＃61;0;
370 lsum&＃61;0;
371 ldfs(sx,sy,f);
372 cout<" ";
373 flag&＃61;0;
374 rsum&＃61;0;
375 rdfs(sx,sy,f);
376 cout<" ";
377 bfs(sx,sy);
378 }
379 return 0;
380 }