I'm really struggling to solve problem #5 from the South African Programming Olympiad 2007. please help by sharing an approach, algorithm or program.
Proposed & Prepared by Marco Gallotta
Fred the manic store-keeper can't keep up with the growing size of his store. He wants to know how many rooms he has and the size of the smallest and largest ones. However, his store is too large for him to work out on his own, so he has asked for your help.
Fred has given you the plans of his store. In the plans, a wall is represented by a '1' and a floor tile by a '0'. Your task is to write a program to group neighbouring floor tiles into rooms. A tile can be grouped together with all tiles one space directly to its left, right, top and bottom. Note that this does not include diagonals. A room is defined as a group of floor tiles that cannot be grouped together with any further floor tiles.
Given the plans your task is to work out:
- The total number of rooms
- The size of the smallest room
- The size of the largest room.
1 <= width, height <= 20.
Enter width: 3
Enter height: 2
Enter row: 001
Enter row: 010
Number of rooms: 2
Smallest room: 1
Largest room: 3