CCC '03 S3 - Floor Plan

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 64M
Problem type
Canadian Computing Competition: 2003 Stage 1, Junior #5, Senior #3

The floor plan of a house shows rooms separated by walls. This floor plan can be transferred to a grid using the character I for walls and . for room space. Doorways are not shown. Each I or . character occupies one square metre.

In this diagram there are six rooms.

You have been given the floor plan of a house and a supply of hardwood flooring. You are to determine how many rooms will have the flooring installed if you start installing the floor in the largest room first and move to the next largest room, and so on. You may not skip over any room, and you must stop when you do not have enough wood for the next room. Output the number of rooms that can have hardwood installed, and how many square metres of flooring are left over. No room will be larger than 64 square metres.

The first line contains the number of square metres of flooring you have. The second line contains an integer r in range 1 \ldots 25 that represents the number of rows in the grid. The third line contains an integer c in 1 \ldots 25 that represents the number of columns in the grid. The remaining r lines contain c characters of grid data.

Sample Input 1

105
14
16
IIIIIIIIIIIIIIII
I......I.......I
I......III.....I
I........I.....I
I........IIIIIII
IIIIIIIIII.....I
I.I......I.....I
III..III.I.....I
I....I.IIIII...I
I....I.....III.I
I....I.......I.I
I....I.....III.I
I....I.....I...I
IIIIIIIIIIIIIIII

Output for Sample Input 1

4 rooms, 1 square metre(s) left over

Sample Input 2

13
2
3
.I.
.I.

Output for Sample Input 2

2 rooms, 9 square metre(s) left over

Comments


  • -9
    Narcariel  commented on Dec. 16, 2020, 9:31 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • -21
      jman579  commented on Dec. 16, 2020, 12:35 p.m. ← edited

      This comment is hidden due to too much negative feedback. Click here to view it.


      • 11
        Narcariel  commented on Dec. 16, 2020, 4:44 p.m.

        Hey Jman, I really like your floor plan solution can you send me the GitHub link you used?


  • 10
    nathancoulas2003  commented on May 12, 2020, 1:04 a.m. ← edited

    Be sure to remember that the judge is strict so your output should be exact. This includes not spelling "metre" as "meter" like I did.


  • 38
    jaihysc  commented on Nov. 27, 2019, 7:54 p.m. ← edited

    Remember that 1 room should be room not rooms


  • -17
    DarthVader336  commented on Oct. 29, 2019, 1:05 a.m. ← edited

    This comment is hidden due to too much negative feedback. Click here to view it.


  • 0
    Suraj_IOI  commented on May 30, 2019, 1:10 p.m. ← edit 8

    Kirito What is wrong with my solution ? I am getting correct answer on my system but WA here.


  • -7
    Newbie  commented on June 1, 2018, 12:51 a.m. ← edit 3

    This comment is hidden due to too much negative feedback. Click here to view it.


  • 2
    m4m3sh1b4  commented on Dec. 13, 2017, 11:21 p.m.

    If you have this map,

    IIII

    I.II

    II.I

    IIII

    is it one room or two?


    • 5
      ZippIE  commented on Dec. 14, 2017, 12:03 p.m.

      There are 2 rooms.


  • 0
    Kevin_Pan  commented on Aug. 12, 2016, 10:09 p.m. ← edit 3

    nvm, forgot about 0 rooms


  • -5
    bobhob314  commented on Jan. 9, 2015, 4:00 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 37
      Xyene  commented on Jan. 10, 2015, 11:36 a.m.

      The statement implies that a room does not have diagonal walls, and in a real-world scenario you can't move between cracks in walls anyways.


  • -1
    kobortor  commented on Dec. 3, 2014, 9:08 p.m.

    Should we print 0 meters left over?


    • -1
      kobortor  commented on Dec. 3, 2014, 10:15 p.m.

      Never mind, there aren't any such cases it seems


      • -1
        Rich123  commented on July 10, 2015, 9:28 a.m.

        What would you do if there is 0 flooring left over?


        • -13
          kobortor  commented on July 10, 2015, 12:00 p.m.

          This comment is hidden due to too much negative feedback. Click here to view it.


  • 122
    Xyene  commented on Nov. 29, 2014, 11:17 p.m.

    If there is only 1 room, "rooms" should not be pluralized.


    • 50
      root  commented on May 7, 2017, 5:33 p.m.

      This should seriously be in the problem statement


    • 11
      STA  commented on Dec. 3, 2014, 3:28 p.m.

      Thanks for the hint.