#1103 - Ancient Messages
|Algorithms Used:||other graph|
|Solution Description: ||The key thing to notice in this problem is that each of the 6 shapes has a different number of holes. "Was" has no holes, "Ankh" has one, ..., "Djed" has five.|
So this problem boils down to finding contiguous sets of black pixels and determining how many holes are inside.
First, look for white pixels on the border of the image. These are definitely background pixels. Floodfill all white pixels from these to find all background pixels.
Now we'll do a double-floodfill. First, scan the image for black pixels. When you find one, floodfill outwards looking for black pixels, and white pixels that aren't part of the background. When you find such a white pixel, floodfill for all white pixels that it's connected to, and mark this as one hole. Then, go back to flooding black pixels.
Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By