2003 Canadian Computing Competition, Stage 1

Problem J5/S3: Floor Plan

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 of the input contains the number of square metres of flooring you have. The second line in the input contains an integer r from 1 to 25 that represents the number of rows in the grid. The third line contains an integer c from 1 to 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

Sample Output 1

4 rooms, 1 square metre(s) left over

Sample Input 2

13
2
3
.I.
.I.

Sample Output 2

2 rooms, 9 square metre(s) left over

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 02, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

If there's only 1 room, output "room" not "rooms".

yes, i had the same problem

Since the grid can be at most 25x25, then we can calculate there can be 13 rooms every other column and 13 rooms every other row, so there's a theoretical limit of 14*14 = 196 rooms.

Thanks :D

Do you still need to output "square meters left over"?

Yes, you should still output "0 square metre(s) left over"

alright, thanks

Does it mean nothing larger than 64 meters squared or 64 squared meters (64m^2 or 4096m^2)? I mean should it be an array [64][64] max? Or does it mean the individual rooms?

64 square meters is a unit of area, not length. You shouldn't be using an array[64][64] when they give you the restraints for both row and column numbers. It says "No room will be larger than", so I'm guessing individual rooms.

Hope this helps.

Thanks :D

I didn't get "square metre(s) left over" term in question.Can anybody explain how 9 is answer in second case??

The first variable in the input is how much flooring you have at your disposal. So for each '.' tile you use up 1 square meter of this flooring. 

Hi, I'm fairly new to this website, which is great so far! Thank you.  I used a floodfill algorithm but got an RE.  Do you guys know what that means?

[b]RE[/b] is [b]R[/b]untime [b]E[/b]rror. It sometimes means that you've exceeded memory limits (moreso in C++). It can also mean you've gone out of bounds, or that you've tried to perform an invalid conversion.

Logical1111 on Nov 27, 2008 - 12:46:36 am UTC Exclamation!!!!

• (3/16)

mini wedding juicer!!!!

mini wedding juicer!!!!

jargon on Nov 27, 2008 - 1:23:52 am UTC Re: Exclamation!!!!

• (2/2)

Please try not to triple-exclamation your posts... it's a bit annoying after you realize you've done that on EVERY post... :twisted:

Please try not to triple-exclamation your posts... it's a bit annoying after you realize you've done that on EVERY post...

taimla101 on Jan 21, 2009 - 4:30:17 am UTC Re: Exclamation!!!!

• (2/0)

not even close

not even close

? this problem is so easy -.-
especially after they taught recursion in class lol

but recursion is still a fairly hard topic for some of us, and worth more than 5 points for everyone exept hanson

The point value of a problem depends on the amount of thought that has to go into writing a solution. Besides, we showed you blob removal in class.