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

    ACM-POJ EXP 157阅读 0评论

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


    大致题意

    墙上有一面黑板,现划分为多个矩形,每个矩形都要涂上一种预设颜色C。

    由于涂色时,颜料会向下流,为了避免处于下方的矩形的颜色与上方流下来的颜料发生混合,要求在对矩形i着色时,处于矩形i上方直接相邻位置的全部矩形都必须已填涂颜色。

    在填涂颜色a时,若预设颜色为a的矩形均已着色,或暂时不符合着色要求,则更换新刷子,填涂颜色b。


    注意

    1、 当对矩形i涂色后,发现矩形i下方的矩形j的预设颜色与矩形i一致,且矩形j上方的全部矩形均已涂色,那么j符合填涂条件,可以用 填涂i的刷子对j填涂,而不必更换新刷子。

    2、 若颜色a在之前填涂过,后来填涂了颜色b,现在要重新填涂颜色a,还是要启用新刷子,不能使用之前用于填涂颜色a的刷子。

    3、 若颜色a在刚才填涂过,现在要继续填涂颜色a,则无需更换新刷子。

    4、 矩形着色不能只着色一部分,当确认对矩形i着色后,矩形i的整个区域将被着色。

    首先要注意输入数据,每个矩形信息的输入顺序是 y x y x c,而不是 x y x y c

    若弄反了x y坐标怎样也不会AC的…..

    解题思路

    拓扑思想+DFS

    方法还是很直观的,把每个矩形看作一个点,处于黑板最上方的矩形i入度为0,然后从矩形i出发,与其下方直接相邻的矩形连线,这些矩形的入度+1。换而言之,矩形a上方直接相邻的矩形数upNum,就是矩形a(点a)的入度数upNum。

      当矩形i被涂色后,矩形i下方直接相邻的所有矩形的入度数-1。

      那么若一个矩形的入度数为0时,它就是待涂色状态;入度不为0则不允许涂色。

      然后就是按照题目要求的涂色限制条件,DFS涂色方案了,数据量较少,无需剪枝也能AC。


    最后说说怎样判定矩形a在矩形b的上方

    矩形a与矩形b的基本位置关系共有3种,如下图:

    设矩形左上角的坐标为(Lx,Ly) 右下角的坐标为(Rx,Ry)

    则先判断Rect[a].Ry==Rect[b].Ly,确定矩形a的底部和矩形b的顶部是否可能重合(直接相邻)


    然后再判断3种情况:

    情况1:

      Rect[a].Lx>=Rect[b].Lx && Rect[a].Lx<Rect[b].Rx

    情况2:

      Rect[a].Lx<=Rect[b].Lx && Rect[a].Rx>=Rect[b].Rx

    情况3:

      Rect[a].Rx>Rect[b].Lx && Rect[a].Rx<=Rect[b].Rx

    注意必须左右方向都要限制,其他特殊情况已由这3种关系所囊括。

    Source修正

    Tehran 1999 (访问需翻墙)

    测试数据

    本文第二页附带测试数据

    测试数据下载


    转载请注明:EXP 技术分享博客 » POJ1691 – Painting A Board

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

    表情

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

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