ACM ICPC World Finals 2011

Problem C: Ancient Messages

This problem may at first glance appear pretty difficult, but the key point is to note that all the different hieroglyphic shapes contain a different number of “holes”. This makes the problem one of the easiest: find the connected regions of the picture and then, for every black region R, count how many different white regions are adjacent to R (making sure to pad the entire picture with a white frame to make the outer region one single region).

A different, more fancy solution, is to use the Euler characteristic to compute the genus of each black region.