Internet Problem Solving Contest

IPSC 2001

Solution to Problem E – A Censored Smile

Easy input for this problem was really easy. It contained only four faces and two of them was smiling. This fact could be observed immediately after opening the input file in the editor.

Difficult input was much bigger, therefore some other method was needed. There are many approaches to solve this problem. The simplest one is to print the input and count faces manually. However, this is quite time consuming and it is very easy to make a mistake in counting. But some teams used this technique succesfully.

The second extreme would be a full automatic solution -- a program that finds all faces and for each face decides, wheter it is smiling or not. It is not trivial to implement all rules for recognizing smiling faces. Therefore this was not an optimal solution.

Probably the best method in the competition was a semi-automatic solution. It is easy to write a program, that finds distinct faces and for each face writes number of its occurences in the input. Because in the input there was only few distinct faces (about 10), its easy to count smiling faces from the output of this program.

So, the program can work in the following way: After reading the input file it fills squares, that are not inside some face. This can be done for example by depth-first search started from borders of the input bitmap. In this search, 4-neighbourhood has to be used.

Next, distinct faces are searched. Program is scanning the whole bitmap. Finding a non-filled square means, that new face was found. This face is filled by depth-first search using 8-neigbourhood. In this search, bounding box of the face (e.g. leftmost, uppermost, rightmost and lowermost square in the face) is found.

Newly found face is compared with all previously found faces. If the face is distinct from all others, new kind of face was found. Otherwise, only number of occurences of the face is updated. Comparing of the faces can be done by comparing of the content of whole bounding boxes. This is not exact, because bounding boxes of two faces can overlap. The result is, that one kind of face can appear more than once in the output of the program. But it is easier to solve this obstacle manually than to write advanced program.