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

    ACM-POJ EXP 182阅读 0评论

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


    大致题意

    哈哈,玩过“GBA口袋怪兽”的同学看到这题都应该非常容易理解了,“游戏也不过是这样写出来的”O(∩_∩)O哈~

    题意不难懂,我大致翻译一下:

    就是要求把一个冰壶从起点“2”用最少的步数移动到终点“3”

    其中0为移动区域,1为石头区域,冰壶一旦想着某个方向运动就不会停止,也不会改变方向(想想冰壶在冰上滑动),除非冰壶撞到石头1 或者 到达终点 3

    注意的是

    冰壶撞到石头后,冰壶会停在石头前面,此时(静止状态)才允许改变冰壶的运动方向,而该块石头会破裂,石头所在的区域由1变为0. 也就是说,冰壶撞到石头后,并不会取代石头的位置。

    终点是一个摩擦力很大的区域,冰壶若到达终点3,就会停止在终点的位置不再移动。

    解题思路

    其实与其说这是深搜题,我觉得更像模拟题。。。

    要先明确:

    0为滑动区域

    1为石头区域

    2为起点,也是可滑动区域

    3为终点,不可滑动区域

    (1) 起点为“2”,也是一个可滑动的区域,所以标记起点位置之后,可以把起点当做0

    (2) 注意区分冰壶是运动的还是静止的,若是静止的话,旁边1格有石头是不能走的。

    (3) 输出冰壶从2到3的最短路,如果最短路的步数大于10(不包括10),视作无法走到终点(其实这是用来剪枝的

    (4) 滑动过程中冰壶不允许出界

    基于上面的原则,不难发现:

    (1)所谓的“走一步”,就是指冰壶从一个静止状态到下一个静止状态,就是说冰壶在运动时经过的“格数”不视作“步数”,也就是说冰壶每次移动的距离都是不定的。

    (2)还有就是由于石头会因为冰壶的碰撞而消失,因此冰壶每“走一步”,场地的环境就会改变一次。

    (3)基于(2),可以发现本题虽然是要找 “最短路”,但是BFS几乎不可能,因为每“走一步”,场地的状态就要改变一次;而如果该步不满足要求,又要求把场地的状态还原到前一步,这只有DFS能做到。

    (4)基于(3),DFS不是BFS,不能简单地用它来找最短路,必须要把所有可能的路一一找出来,再逐一比较它们的步数才能确定最短。但题目值允许1000MS,此时就面临一个超时的问题。所以题目才同时给出“步数超过10则视为失败”的条件,这是用来剪枝


    有了上面的分析,就能最终确定本题的解法了:

    有2种方法

    DFS+Vector+剪枝

    DFS+回溯+剪枝

    但是由于POJ对STL的“兼容性”很差,我用STL就没见过不TLE的题。。。这题也一样,所以不推荐,其实Vector是很好用的,利用它的特性可以在DFS返回上一步时,自动还原场地状态,而回溯法则需要手动还原场地状态(其实也就8行代码)

    DFS用于寻找路径,回溯(或Vector)用于还原棋盘状态,剪枝用于优化

    另外注意的时,如果把冰壶定义为“动静”两种状态,那么搜索时就可以以“格”为单位,+1搜索,详细可以看我的程序,我感觉这样比较简单。我感觉每步都用for找移动的格数会非常烦

    下面我会把两种代码都贴出来,供大家参考。


    方法一:DFS+回溯+剪枝

    转载请注明:EXP 技术分享博客 » POJ3009 – Curling 2.0

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

    表情

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

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