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

    ACM-POJ EXP 1760阅读 13评论

    全解题报告索引目录 -> 【北大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

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

    表情

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

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址
    (13)个小伙伴在吐槽
    1. Greate article. Keep posting such kind of info on your page. Im really impressed by it. Hi there, You've performed a great job. I'll definitely digg it and in my opinion suggest to my friends. I am confident they'll be benefited from this website.
      website marketing2019-05-20 05:45 回复
    2. It's the best time to make some plans for the future and it is time to be happy. I have learn this submit and if I could I wish to counsel you some interesting issues or suggestions. Perhaps you could write subsequent articles relating to this article. I wish to read even more things approximately it!
      seo2019-05-12 23:18 回复
    3. Pretty section of content. I just stumbled upon your web site and in accession capital to assert that I get in fact enjoyed account your blog posts. Any way I will be subscribing to your feeds and even I achievement you access consistently fast.
      accountant2019-03-16 17:50 回复
    4. I’m not that much of a internet reader to be honest but your blogs really nice, keep it up! I'll go ahead and bookmark your site to come back in the future. All the best
      free robux codes2019-03-08 15:51 回复
    5. I know this web site presents quality dependent articles or reviews and other material, is there any other web site which gives these kinds of stuff in quality?
      62019-03-05 00:45 回复
    6. You should take part in a contest for one of the highest quality sites online. I am going to highly recommend this web site!
      匿名2019-02-27 22:04 回复
    7. Good blog you've got here.. It's diffficult to find good quality writing like yours these days. I honestly appreciate people like you! Take care!!
      get private Proxies2019-02-27 11:54 回复
    8. I believe this is among the most important info for me. And i'm glad reading your article. But want to statement on few common issues, The web site style is great, the articles is actually excellent : D. Just right job, cheers
      Dsite2019-02-25 04:53 回复
    9. What a material of un-ambiguity and preserveness of precious familiarity about unpredicted emotions.
      download2019-02-13 03:25 回复
    10. Do you have any video of that? I'd like to find out more details.
      best travel websit2019-02-11 11:32 回复
    11. Great blog here! Additionally your site so much up very fast! What web host are you the usage of? Can I get your associate hyperlink in your host? I want my site loaded up as fast as yours lol
    12. Hmm it looks like your website ate my first comment (it was super long) so I guess I'll just sum it up what I wrote and say, I'm thoroughly enjoying your blog. I as well am an aspiring blog blogger but I'm still new to the whole thing. Do you have any tips for beginner blog writers? I'd certainly appreciate it.
    13. What's up to every single one, it's truly a pleasant for me to pay a quick visit this web site, it consists of helpful Information.
      lanqiuming2019-01-08 04:37 回复