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

    ACM-POJ EXP 153阅读 0评论

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


    大致题意

    在一个y行 x列的迷宫中,有可行走的通路空格" ",不可行走的墙"#",还有两种英文字母A和S,现在从S出发,要求用最短的路径L连接所有字母,输出这条路径L的总长度。

    解题思路

    BFS+Prim

    一格的长度为1,而且移动的方法只有上、下、左、右,

    所以在无任何墙的情况下(但“墙#”是必须考虑的,这里只是为了说明)

    任意两个字母之间的距离就是直接把 横坐标之差 加上 纵坐标之差

    注意的是:
      ① 可行的路为 字母 和 空格
      ② 不可行的路为 # 和 矩阵范围之外

    根据题意的“分离”规则,重复走过的路不再计算

    因此当使用prim算法求L的长度时,根据算法的特征恰好不用考虑这个问题(源点合并很好地解决了这个问题),L就是最少生成树的总权值W

    由于使用prim算法求在最小生成树,因此无论哪个点做起点都是一样的,(通常选取第一个点),因此起点不是S也没有关系

    所以所有的A和S都可以一视同仁,看成一模一样的顶点就可以了

    最后要注意的就是 字符的输入

    cin不读入空字符(包括 空格,换行等)

    gets读入空格,但不读入换行符)

    剩下的问题关键就是处理 任意两字母间的最短距离,由于存在了“墙#” ,这个距离不可能单纯地利用坐标加减去计算,必须额外考虑,推荐用BFS(广搜、宽搜),这是本题的唯一难点,因为prim根本直接套用就可以了


    求 任意两字母间的最短距离 时 不能直接 用BFS求,

    1、必须先把矩阵中每一个允许通行的格看做一个结点(就是在矩阵内所有非#的格都作为图M的一个顶点),对每一个结点i,分别用BFS求出它到其他所有结点的权值(包括其本身,为0),构造结点图M;

    2、然后再加一个判断条件,从图M中抽取以字母为顶点的图,进而构造字母图N

    这个判定条件就是当结点图M中的某点j为字母时,把i到j的权值再复制(不是抽离)出来,记录到字母图N的邻接矩阵中

    3、剩下的就是对字母图N求最小生成树了

    转载请注明:EXP 技术分享博客 » POJ3026 – Borg Maze

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

    表情

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

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