很经典的BFS搜索 走迷宫选取经过门最少的路线,这题POJ测试数据设计不全面,changeDir数组赋值错误也可以过。。。
主要图的数据结构存储方式和算法实现参考了http://blog.csdn.net/bobten2008/article/details/5093307
(1)首先是建图, 由于输入给的都是线段, 但是我们平常处理这类问题都是转换为网格来做的, 因此需要将线段转换为网格.转化的方法是对于每个格子,用其左上角点的坐标来表示这个格子。如果其左上角点的坐标是[i][j],那么这个格子就表示为[i][j].将其四周边界的四条线段归这个格子管.即为每个格子建一个数组round[i][j][4],第三维的四个位置分别表示这四条线段的类型(0-3分别对应上下左右):
数组元素的值0表示空气,1表示墙,2表示是一扇门,这样这个模型就建立好了.
(2)其次是bfs的起始点选为Nemo所在的位置,注意要将这个浮点点位置转化为格子的坐标.转化的方法很简单.对于x坐标取整即可,对于y坐标取整+1即可,比如Nemo所在位置为[1.2, 1.3]那么转化为格子的坐标即为:[1, 2].这个坐标即位bfs遍历的起始点
(3)遍历的时候如果所走的方向是墙,则不可走.如果是门则将当前总的steps数+1,如果为空气,steps数不变.另外一点就是如何判重.判重不能简单地记录有没有被访问过,而是需要记录到当前格子的最小步骤.如果当前总步骤数小于当前格子的最小步骤数,则更新其最小步骤数并将这个格子加入队列中.
(4)遍历的终止位置即为题目中的出发位置[0, 0]
Source Code
Problem: 2049
|
|
User:
yangliuACMer
|
Memory: 1160K |
|
Time: 250MS |
Language: C++ |
|
Result: Accepted
|
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-简单搜索 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
想看看自己的编程能力到底怎么样,很多人都回去做一做POJ的题目吧,在这里你不妨可以先看看它的题目分析。
简单搜索题 数独 答案 POJ 2676 也可以没事玩玩数独。
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
很经典的图论,网络流入门的题目,值得一看啊~~其中有简单的解析
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)