poj3083ChildrenoftheCandyCorn（dfs+bfs)

作者：UTOB | 来源：互联网 | 2023-10-11 12:06

题目：http:poj.orgproblem?id3083这个题吧，没什么难点，就是题意有点难懂，后来问了一下ZPÿ

题目&＃xff1a;http://poj.org/problem?id&＃61;3083

这个题吧&＃xff0c;没什么难点&＃xff0c;就是题意有点难懂&＃xff0c;后来问了一下ZP&＃xff0c;知道了是什么意思后就开始敲了&＃xff0c;敲了一半&＃xff0c;QC让我再去讲题&＃xff0c;结果回到宿舍又把剩下的敲完的

提交&＃xff0c;然后1A

题意主要是&＃xff1a;

给定一个迷宫&＃xff0c;S是起点&＃xff0c;E是终点&＃xff0c;#是墙不可走&＃xff0c;.可以走

先输出左转优先时&＃xff0c;从S到E的步数

再输出右转优先时&＃xff0c;从S到E的步数

最后输出S到E的最短步数

我设置的四个方向是&＃xff0c;面向下为1&＃xff0c;面向左为2&＃xff0c;面向上为3&＃xff0c;面向右为4

代码&＃xff1a;

View Code

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 }

转:https://www.cnblogs.com/wanglin2011/archive/2013/01/23/2874099.html

推荐阅读

io
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
io
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
io
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
io
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
io
Linux环境变量函数getenv、putenv、setenv和unsetenv详解

本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数，可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值，并打印出来。 ... [详细]

蜡笔小新 2023-12-13 12:01:03
io
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
io
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
io
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
io
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
io
c语言\n不换行,c语言printf不换行

$c语言\n不换行,c语言printf不换行$

本文目录一览：1、C语言不换行输入2、c语言的 ... [详细]

蜡笔小新 2023-12-14 11:05:35
io
C函数ispunct()的用法及示例代码

本文介绍了C函数ispunct()的用法及示例代码。ispunct()函数用于检查传递的字符是否是标点符号，如果是标点符号则返回非零值，否则返回零。示例代码演示了如何使用ispunct()函数来判断字符是否为标点符号。 ... [详细]

蜡笔小新 2023-12-13 18:13:34
io
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
io
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
io
Java项目管理工具及配置教程推荐

本文介绍了一些Java开发项目管理工具及其配置教程，包括团队协同工具worktil，版本管理工具GitLab，自动化构建工具Jenkins，项目管理工具Maven和Maven私服Nexus，以及Mybatis的安装和代码自动生成工具。提供了相关链接供读者参考。 ... [详细]

蜡笔小新 2023-12-13 06:45:16
io
C++字符字符串处理及字符集编码方案

本文介绍了C++中字符字符串处理的问题，并详细解释了字符集编码方案，包括UNICODE、Windows apps采用的UTF-16编码、ASCII、SBCS和DBCS编码方案。同时说明了ANSI C标准和Windows中的字符/字符串数据类型实现。文章还提到了在编译时需要定义UNICODE宏以支持unicode编码，否则将使用windows code page编译。最后，给出了相关的头文件和数据类型定义。 ... [详细]

蜡笔小新 2023-12-13 04:59:58

UTOB

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章