Ancient Hieroglyphs
Time limit1sMemory limit192 MB
Decode a hex bitmap, count enclosed white regions (holes) inside each connected black shape, and map each shape's hole count to a hieroglyph code.
- Level
Medium5 of 10
- Topics
- Graph, DFS, BFS, Implementation
- Solved
- No attempts yet
Problem
Archaeologists study writing in ancient languages to understand early civilizations. About years ago, the Egyptians used an ancient script called hieroglyphs, whose characters were modeled on animals, objects, and parts of the body.
In this problem you write a program that recognizes the following six hieroglyphs. Each hieroglyph is a single shape made of connected black pixels, and the six are distinguished by having different numbers of holes (white regions completely enclosed by the shape). In other words, the number of holes alone determines which hieroglyph it is.
Determine every hieroglyph that appears in the given image.
Input
The input consists of several test cases. Each test case is a single image containing one or more hieroglyphs. The image is made of s and s, where is a black pixel and is a white pixel.
Each line of the image is encoded in hexadecimal. For example, the eight pixels are encoded as 9c. The hexadecimal encoding uses the characters 0–9 and a–f.
The first line of each test case contains two integers and . () is the number of image lines and () is the number of hexadecimal characters on each line, so the image is pixels wide. The next lines give the image.
Each input image satisfies the following rules.
- The image contains only the six hieroglyphs described above.
- Every image contains at least one valid hieroglyph.
- Every black pixel is part of some valid hieroglyph.
- A hieroglyph is a connected set of black pixels: every black pixel is adjacent (up, down, left, or right) to at least one other black pixel.
- Distinct hieroglyphs do not touch one another, and no hieroglyph is contained inside another.
- Whenever two black pixels touch diagonally, there is a black pixel that is orthogonally adjacent to both of them.
- A hieroglyph may be somewhat distorted, but its number of holes is always as given in the table above.
The line after the last test case contains two s.
Output
For each test case, print one line in the form Case x: codes, where is the test case number starting from and codes is the string of hieroglyph codes appearing in the image, sorted in alphabetical order.