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

    ACM-POJ EXP 120阅读 0评论

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


    大致题意

    一种类似围棋的游戏,有黑白两种颜色的棋子。

    规定黑棋为先手,白棋为后手。

    放下棋子A后,若A的8个马步方位(即中国象棋的“马”或国际象棋的“骑士”的“日”字走法)至少存在1个同色的棋子,且当连接A与这些棋子时,其连线不切割已经有的线,则连接。

    黑棋的目标是连出一条从X轴的0列到N列的路;

    白棋的目标是连出一条从Y轴的0行到N行的路。

    就是说某一方要赢棋,当且仅当其把自己的两个“终域”连接在一起,完全阻隔对方的连接。

    按照以上规则,判断黑棋所走的最后一步是否为赢棋的一步。

    解题思路

    比较麻烦的模拟,但是难度不大,难点主要在于判断连线是否相交。

    如上图放下一只棋子后,先检查其附近的8个方位是否存在同色棋子,若存在,则检查是否允许与该同色棋子连线。

    检查连线方法如下图,以30度的方位为例:

    如上图,当放下新棋子后,若检测到30度方位存在与其同色的棋子,则在连接蓝线之前,先检查是否已存在9条红色的线,当且仅当这9条红线都不存在时,才允许连接蓝线。

    其他7个方位也是同样做法。

    最后要判断黑棋的最后一步是不是为赢棋的一步,只需要做两次BFS

    第一次BFS:以黑棋的0终域为起点,寻找是否存在到N终域的路。

    第二次BFS:先删去最后一步棋,再以黑棋的0终域为起点,寻找是否存在到N终域的路。

    当第一次BFS结果为true,第二次BFS结果为false时,则说明黑棋的最后一步为赢棋的一步

    Source修正

    Mid-Central USA 2005(已失效)

    测试数据

    本文第二页附带测试数据

    转载请注明:EXP 技术分享博客 » POJ2706 – Connect

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

    表情

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

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