存档

文章标签 ‘BFS’

POJ 2251 Dungeon Master[三维BFS]

2011年9月10日 7 条评论

题目大意:给定一个三维的迷宫,看看能不能从起点走到终点,如果能的话就求出最短的时间(每次移动耗费一个时间单位)。
解题思路:还是搜索,只不过多加了一层;普通的搜索通常是二维情况下的,也就是在一个平面内进行搜索;而这个题目中的搜索范围是一个三维空间;考虑到求最短时间,所以可以用BFS作为搜索方法;二维也好三维也好,BFS的本质是不变的,只是增加了一个向上和向下的移动方向而已。
传送:POJ 2251 Dungeon Master http://poj.org/problem?id=2251
解题代[......]

继续阅读

分类: POJ解题报告 标签: , ,

POJ 1915 Knight Moves[BFS]

2011年9月2日 没有评论

Knight问题,这个题比较好,给了个图说明了Knight的运行规则。这类题一般都是BFS做啦,可以定义一个数组存放移动的方法,这样更加方便。
更多题目:
POJ 1915 Knight Moves http://poj.org/problem?id=1915
POJ 2243 Knight Moves http://poj.org/problem?id=2243
POJ 2488 A Knight’s Journey http://poj.org/problem?id=2488
解[......]

继续阅读

分类: POJ解题报告 标签: ,

POJ 3278 Catch That Cow[BFS]

2011年9月2日 没有评论

复习数据结构ing,现在做做简单的题目。这是很久以前做的入门的题,翻出来了。用BFS做,如果只用一个队列,那么需要定义结构体来存储节点的位置信息和时间信息;如果不想用结构体的话需要两个队列,这样是一层一层的遍历节点,就只需要一个整型来记录时间信息了。其实都差不多,具体实现手法不同而已,BFS的思想是不变的。
下面两个版本的代码都贴一下,
POJ 3278 Catch That Cow[BFS] [http://poj.org/problem?id=3278]

#include <iost[......]

继续阅读

USACO The Clocks|BFS

2010年12月1日 3 条评论

The Clocks一题看完之后第一个想到的就是BFS(其实很有多方法可以解决,有兴趣可以去参考参考NOCOW的解题代码)。对于这样的BFS,我都是定义结构体来作为节点,像本题中使用一个state字符串来记录当前的状态,然后最开始用了一个vector来记录已经出现过的状态,结果在提交的时候悲剧的TLE了。
于是各种加优化,想了想,中间产生大量状态,然后每次都从头到尾的搜索vector效率是低了点(对于vector来说,全局的find函数是O(N)的复杂度),于是改用map,map排序了,复杂度O[......]

继续阅读

分类: USACO题解 标签: , , , , ,