KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up


Problem I. 183. (March 2008)

I. 183. Once upon a time, the government of a not-so-distant country decided to cut back on hospital supply expenses. Worn bed-linen are darned using a high-end hole detector. After the resolution is set appropriately, this device determines whether a given cell of the sheet is punctured. (Edges are strong enough not to contain any holes.)

The value of a given cell is V if the fabric is intact, and L, if there is a hole there. Each hole should be covered by a rectangle of new material (with sides parallel to the edges of the sheet). A group of L's belong to the same hole, if each L in the group has at least one edge in common with another L in the same group. A letter L belongs to a different hole if it is not adjacent at all, or if it only touches the corner of an L from the other hole. Rectangles can overlap each other. (The figure ``Példa két lyukas területre'' shows a sheet with two holes.)

Prepare your program which gives the number of patches to be sewn on the sheet. The name of the input file describing the sheet is the first command line argument of your program. The standard output should be used to list the number of patches in order by specifying the top left and bottom right corners of each rectangle. (First the row, then the column coordinate should be specified for each corner, relative to the top left corner of the sheet.)

The first and second lines of the input file contain two integers N and M (3\leN\le200, 3\leM\le200), giving the total number of rows and columns on the sheet. The following N lines contain M characters, either a V or an L.

The ``Példa (berajzolt foltokkal)'' part of the example is a sample input, Kimenet is the output. ``Folt'' means patch.

The source code of your program (i183.pas, i183.cpp, ...) and a short documentation (i183.txt, i183.pdf, ...) should be submitted containing a description of your solution and specifying the developer environment to compile your code.

(10 pont)

Deadline expired on 15 April 2008.


7 students sent a solution.
10 points:Adrián Patrik, Földes Imre, Szoldatics András, Véges Márton.
5 points:1 student.
4 points:2 students.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley