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
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
io
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
io
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
search
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
io
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
char
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
io
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
io
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
go
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
io
使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表

本文介绍了一段通用代码示例，该代码不仅能够操作 Azure Active Directory (AAD)，还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级：AAD 和 Subscription。 ... [详细]

蜡笔小新 2024-12-27 16:07:12
io
C语言实现小写金额转换为大写金额

在金融和会计领域，准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据，还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法，确保数据的标准化和规范化。 ... [详细]

蜡笔小新 2024-12-27 12:39:06
io
ImmutableX Poised to Pioneer Web3 Gaming Revolution

ImmutableX is set to spearhead the evolution of Web3 gaming, with its innovative technologies and strategic partnerships driving significant advancements in the industry. ... [详细]

蜡笔小新 2024-12-27 08:55:17
io
使用Vultr云服务器和Namesilo域名搭建个人网站

本文详细介绍了如何通过Vultr云服务器和Namesilo域名搭建一个功能齐全的个人网站，包括购买、配置服务器以及绑定域名的具体步骤。文章还提供了详细的命令行操作指南，帮助读者顺利完成建站过程。 ... [详细]

蜡笔小新 2024-12-26 16:36:34
io
C语言链表动态创建：头插法与尾插法详解

本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法，包括具体的实现代码和运行示例。通过这些内容，读者可以更好地理解和掌握链表的基本操作。 ... [详细]

蜡笔小新 2024-12-26 13:59:07
io
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16

UTOB

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

Tags | 热门标签

RankList | 热门文章