1st Balkan Olympiad on Informatics
Constantza, Romania, 24-29 May 1993

Day 1 - Problem 1 (40 points)

Let us consider a bidimensional array A with m rows and n columns, whose elements are 0 or 1, 0 representing the background (paper), 1 representing the color of the design (ink). The design is made of several objects. By "objects" we understand a set of elements of the same type ink (1), each element having at least a neighbor on the directions above,below, left, right or on one of the diagonals. Any two objects are separated by elements of the same type paper (0).

Determine the rectangle of minimum area which contains a maximal object (i.e. the one whose number of elements of type ink (1) is maximal). (15 points)

Place the object found at (a) in the areas of the array which are not occupied by other objects, so that it can be placed in as many places as possible without destroying the other objects already placed. (25 points)