IARCS home > OLYMPIAD > Archives
Chambers in a castle next up previous
Next: Input format Up: inoi2003-qpaper Previous: Instructions

Chambers in a castle

The floor plan of a castle indicates where the walls are. The outer boundary of the castle is always an unbroken wall. The castle has no doors, only openings in the walls that lead from one room to another. A chamber is a collection of rooms that are connected to each other by gaps in the walls. The problem is to:

  1. Count the number of chambers in the castle.

  2. Calculate the area of the largest chamber.

To simplify the problem, the floor of the castle is divided into square tiles. All walls lie at tile boundaries. The area of a chamber is specified in terms of the number of tiles inside the room (without counting the tiles occupied by the surrounding walls).

Figure 1 is an example of a floor plan. Each square is a tile. White tiles represent open space, while black tiles represent walls. In this castle, there are four chambers. The largest chamber has an area of 58.

$\textstyle \parbox{7cm}{ \epsfxsize=7cm \epsfbox{castle.eps} }$


Figure 1


Subsections
next up previous
Next: Input format Up: inoi2003-qpaper Previous: Instructions
Madhavan Mukund 2003-05-22



Copyright (c) IARCS 2003-2024;   Last Updated: 23 May, 2003