• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3083 – Children of the Candy Corn

    ACM-POJ EXP 202阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    题目大意

    给定一个迷宫,S是起点,E是终点,”#”是墙不可走,”.”可以走

    先输出左转优先时,从S到E的步数

    再输出右转优先时,从S到E的步数

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

    W为宽,列数

    H为高,行数

    解题思路

    DFS和BFS的综合题水题,难度不大,但是写代码时要注意几方面:

    1、 左转、右转优先搜索时必须标记当前位置时的方向,我定义的方向是

    最初的方向由起点S确定,而下一步的方向则由前一步的走向决定

    例如 左边优先搜索:

    当前位置的方向指向 1(向左),(这同时说明前一步是在第“3”的位置走过来的)

    那么走下一步时,就要根据2103的顺序,先逐格确定当前位置周边的四格是否可行

    若第一次确认2可行,就走到2,在位置2时的方向为2(向下)

    若2不可行,则再确定1,若1可行,就走到1,在位置1时的方向为1(向左)

    若1也不可行,则再确定0,若0可行,就走到0,在位置0时的方向为0(向上)

    若0也不可行,说明进入了迷宫的死胡同,要从原路返回,走回3

    右边优先搜索也同理。

    根据我定义的方向,设当前位置为d,那么

    左转,用数学式子表达就是 d=(d+1)%4

    右转,用数学式子表达就是 d=(d+3)%4

    我比较懒,在我的程序中,DFS和BFS都用了多入口的做法,有兴趣的同学可以利用我给出的这两个式子对代码进行优化。

    这里有一点必须要注意的:

    左边、右边优先搜索都不是找最短路,因此走过的路可以再走,无需标记走过的格


    2、寻找最短路只能用BFS

    因此在做第3问时别傻乎乎的又用DFS,DFS对于样例的输入确实和BFS得到的结果一样的,别以为样例PASS就提交了。。。所以我就说样例没代表性,学会测试数据很重要= =

    注意有一点:

    要求E的最短路,必须把迷宫模拟为树,S为根,找到E所在的层(树深),该层就是S到E的最短路,处理技巧就是在BFS时,令queue[tail]的depth等于对应的queue[head]的depth+1,详细见我的程序

    把循环的次数作为深度就铁定错的

    转载请注明:EXP 技术分享博客 » POJ3083 – Children of the Candy Corn

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址