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

    ACM-POJ EXP 206阅读 0评论

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


    大致题意

    某种卫星使用一种叫做“run length encoding”的方式来储存大尺寸图片,

    有一种简单的 edge detection 算法 是将 图像中的每一个点的值与他周围的八个点相减,然后记录下绝对值最大的,上面的右图是左图经过这种算法转换之后的结果。

    现在你的任务就是实现这个算法,输入的图片是以 run length encoding 的形式表示的,同时也要求转换后的图片也以 run length encoding 的形式表示。

    解题思路

    非常令人纠结的模拟题

    由于图片宽度可能为10^9,因此不能开数组,会MLE

    又因为像素点很多,不能直接暴力,会TLE

    突破点在于Input的pair,pair上限只有1000,数据量是最少的,因此只能利用这点去解题。

    要利用pair,就必须懂得“跳跃式编码”,就是说只在像素发生变化的位置进行编码,而像素没有变化的位置则其编码值与其左边的像素一致。


    我只说解题方法,不给证明了。

    先给所有像素点pix顺序标号pos,从1开始,以这个标号pos作为该像素点pix的索引

    利用pos去模拟pix在二维图片的坐标row=(pos-1)/width,col=(pos-1)%width

    这样就无需定义二维数组,仅仅虚构了一个二维数组,就解决了空间溢出MLE的问题

    接下来在 像素发生变化的位置(下面称为“边界”)的地方 编码

    边界位置其实就是每对pair的个数决定的,对边界位置及其周遭共9个像素点编码,把编码结果及对应的索引pos都存放在OutMap,编码方法就是题目给出的算法

    最后把OutMap中的编码值根据其索引值进行升序排序,依次读取OutMap中的编码值,当编码值code发生变化时,则用 变化后的编码索引 减去 变化前的编码索引,就是code在OutMap中出现的次数。

    Source修正

    Mid-Central USA 2000(已失效)

    测试数据

    本文第二页附带测试数据


    转载请注明:EXP 技术分享博客 » POJ1009 – Edge Detection

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

    表情

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

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