Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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 April 15, 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.

Problems in Information Technology of KöMaL, March 2008