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

    ACM-POJ EXP 3228阅读 40评论

    全解题报告索引目录 -> 【北大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,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址
    (40)个小伙伴在吐槽
    1. I intended to create you the very little observation so as to thank you very much the moment again for all the remarkable solutions you've discussed on this page. This is certainly particularly generous of people like you to grant freely precisely what most of us could possibly have made available as an e book to end up making some cash for their own end, certainly given that you could possibly have done it in the event you desired. These good ideas also acted like the fantastic way to comprehend the rest have a similar keenness just like my personal own to learn more and more concerning this matter. I am certain there are a lot more pleasurable sessions up front for people who read your blog.
      kate spade handbags2019-08-23 20:46 回复
    2. I am also commenting to make you understand what a beneficial encounter my friend's princess undergone going through your web page. She figured out many issues, including what it is like to have an excellent teaching style to make many others completely know chosen very confusing topics. You truly exceeded my desires. Thanks for presenting those valuable, safe, explanatory and as well as fun thoughts on that topic to Emily.
      michael kors handbags2019-08-23 07:31 回复
    3. I truly wanted to construct a quick message in order to thank you for the remarkable ideas you are giving out at this website. My rather long internet look up has now been honored with high-quality facts to talk about with my great friends. I 'd assume that most of us visitors are undoubtedly fortunate to dwell in a wonderful website with so many lovely people with useful solutions. I feel really lucky to have come across your web pages and look forward to tons of more excellent minutes reading here. Thanks once again for a lot of things.
      ultra boost 3.02019-08-23 02:36 回复
    4. Yay google is my queen assisted me to find this outstanding web site!
      Jared2019-08-22 22:02 回复
    5. I definitely wanted to write down a quick word to express gratitude to you for all of the stunning tips and tricks you are giving on this site. My incredibly long internet investigation has now been recognized with excellent information to go over with my company. I would repeat that we visitors are definitely fortunate to dwell in a superb community with so many special people with great secrets. I feel quite lucky to have discovered the web page and look forward to so many more enjoyable times reading here. Thanks a lot once again for all the details.
      michael kors handbags2019-08-22 04:03 回复
    6. I really wanted to post a word to be able to express gratitude to you for those fantastic guidelines you are showing here. My particularly long internet search has finally been honored with awesome insight to talk about with my neighbours. I 'd declare that we website visitors are unequivocally lucky to dwell in a decent community with so many brilliant individuals with very helpful methods. I feel very much privileged to have encountered your entire web page and look forward to so many more enjoyable minutes reading here. Thanks again for everything.
      huaraches2019-08-21 06:13 回复
    7. I in addition to my friends were following the good secrets and techniques found on the blog while unexpectedly got an awful suspicion I never expressed respect to the web site owner for those strategies. Those people appeared to be excited to study them and now have absolutely been loving them. Appreciate your actually being very considerate as well as for making a choice on this sort of decent information millions of individuals are really desirous to learn about. My sincere regret for not expressing appreciation to you sooner.
      adidas tubular shadow2019-08-21 00:44 回复
    8. Needed to put you this very small note to help give thanks over again relating to the magnificent knowledge you've contributed on this website. This is certainly surprisingly generous with people like you to present publicly what exactly many individuals might have advertised for an ebook to end up making some money for their own end, mostly considering that you could have tried it in case you decided. The smart ideas as well worked to be the easy way to know that many people have a similar keenness just like my own to know the truth a whole lot more when it comes to this problem. I am sure there are thousands of more enjoyable opportunities in the future for individuals that read through your blog.
      huaraches2019-08-19 17:14 回复
    9. Great work! That is the type of information that should be shared across the web. Shame on Google for no longer positioning this put up higher! Come on over and talk over with my website . Thanks =)
      Maura2019-08-19 16:59 回复
    10. I am only commenting to make you be aware of of the magnificent experience my wife's daughter developed going through yuor web blog. She even learned plenty of pieces, which include how it is like to have a wonderful coaching mindset to have other folks with no trouble learn about specified impossible matters. You actually exceeded people's expectations. I appreciate you for supplying the beneficial, trustworthy, explanatory and easy thoughts on that topic to Ethel.
      michael kors handbags2019-08-18 20:44 回复
    11. I truly wanted to write down a quick word to be able to express gratitude to you for those precious ways you are giving out on this site. My incredibly long internet research has at the end been paid with professional strategies to write about with my family members. I would say that we site visitors are really lucky to dwell in a wonderful site with many outstanding professionals with beneficial points. I feel truly privileged to have discovered your site and look forward to many more entertaining times reading here. Thanks once again for everything.
      coach handbags2019-08-17 05:25 回复
    12. Howdy just wanted to give you a quick heads up. The words in your content seem to be running off the screen in Safari. I'm not sure if this is a format issue or something to do with internet browser compatibility but I thought I'd post to let you know. The layout look great though! Hope you get the problem solved soon. Cheers!
      Read More....2019-08-16 19:57 回复
    13. Thank you so much for giving everyone an extremely nice opportunity to discover important secrets from this site. It can be very great and packed with a good time for me personally and my office acquaintances to search your web site not less than 3 times in one week to learn the fresh guides you will have. And indeed, I'm actually contented considering the beautiful concepts you serve. Some 3 tips on this page are rather the simplest we have had.
    14. Whats up very nice website!! Guy .. Beautiful .. Wonderful .. I will bookmark your site and take the feeds additionally? I'm satisfied to find numerous helpful information here in the submit, we'd like work out more techniques on this regard, thanks for sharing. . . . . .
      Jade2019-08-15 08:59 回复
    15. Hello! Someone in my Facebook group shared this website with us so I came to take a look. I'm definitely enjoying the information. I'm book-marking and will be tweeting this to my followers! Terrific blog and fantastic design and style.
      www.icyte.com2019-08-14 20:33 回复
    16. My spouse and i got so excited Chris could carry out his investigation because of the ideas he received while using the blog. It is now and again perplexing to simply always be giving for free key points that some other people might have been selling. We grasp we've got the blog owner to appreciate for that. The specific explanations you've made, the straightforward website navigation, the friendships you can make it possible to instill - it's everything fabulous, and it's really leading our son and the family reason why the matter is brilliant, and that is seriously essential. Many thanks for the whole thing!
      jordan shoes2019-08-13 23:58 回复
    17. Hey There. I found your blog using msn. This is a really well written article. I will be sure to bookmark it and return to read more of your useful information. Thanks for the post. I'll certainly return.
      Claude2019-08-13 05:01 回复
    18. At this time it seems like Movable Type is the preferred blogging platform out there right now. (from what I've read) Is that what you're using on your blog?
      Harlan2019-08-12 05:04 回复
    19. Keep up the wonderful work, I read few posts on this website and I conceive that your website is real interesting and contains bands of wonderful information.
      Dorothy2019-08-11 18:01 回复
    20. If some one wishes expert view on the topic of blogging and site-building after that i recommend him/her to go to see this blog, Keep up the good work.
      Cedric2019-08-04 05:50 回复
    21. I simply wanted to compose a brief word in order to say thanks to you for some of the lovely items you are placing here. My rather long internet investigation has now been compensated with really good content to write about with my companions. I would mention that most of us readers actually are undoubtedly blessed to live in a decent site with very many brilliant people with very beneficial ideas. I feel somewhat privileged to have discovered the site and look forward to plenty of more awesome minutes reading here. Thanks again for everything.
      fila2019-08-03 11:17 回复
    22. Terrific work! That is the kind of info that are meant to be shared across the net. Shame on the seek engines for now not positioning this submit higher! Come on over and visit my site . Thank you =)
      Lilia2019-08-02 13:05 回复
    23. Heya i am for the primary time here. I found this board and I to find It really helpful & it helped me out a lot. I hope to offer something back and aid others like you helped me.
      hemorrhoids advice2019-08-02 00:14 回复
    24. Hey There. I found your blog using msn. This is an extremely well written article. I'll be sure to bookmark it and come back to read more of your useful info. Thanks for the post. I will definitely return.
      Maricela2019-08-01 06:04 回复
    25. I wanted to construct a quick remark in order to thank you for the amazing recommendations you are writing at this website. My long internet search has at the end been recognized with beneficial concept to write about with my companions. I 'd assert that we site visitors actually are very much lucky to live in a magnificent website with many brilliant professionals with useful tips. I feel quite blessed to have encountered your entire web site and look forward to many more cool moments reading here. Thank you once more for a lot of things.
      stephen curry shoes2019-07-31 05:57 回复
    26. Yay google is my queen aided me to find this outstanding web site!
      Ouida2019-07-30 15:43 回复
    27. I precisely desired to appreciate you all over again. I do not know what I would have done without the creative ideas documented by you directly on this subject matter. It had become the distressing concern for me, but finding out a specialized tactic you treated that took me to jump with delight. Extremely happy for this assistance as well as hope you comprehend what a great job you are getting into instructing many others via your web page. Most likely you haven't got to know all of us.
      hermes belt2019-07-30 08:41 回复
    28. Thank you for all your efforts on this site. Kate takes pleasure in engaging in internet research and it's obvious why. My partner and i hear all concerning the lively means you render simple thoughts through the blog and as well as strongly encourage participation from people on that idea so our girl is really understanding a whole lot. Have fun with the remaining portion of the new year. Your performing a stunning job.
    29. 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 回复
    30. 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 回复
    31. 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 回复
    32. 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 回复
    33. 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 回复
    34. 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 回复
    35. 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 回复
    36. 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 回复
    37. Do you have any video of that? I'd like to find out more details.
      best travel websit2019-02-11 11:32 回复
    38. 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
    39. 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.
    40. 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 回复