The die is cast
InterviewTime limit1sMemory limit128 MB
Given a grid picture of dice drawn with background, die, and dot pixels, count the connected dot regions inside each connected die region and print the counts sorted.
- Level
Medium4 of 10
- Topics
- DFS, BFS, Graph, Implementation
- Solved
- No attempts yet
Problem
A camera takes a picture of several thrown dice, and from that image alone we must count how many dots (pips) are showing on each die.
Each image contains only three kinds of pixels: background pixels, die pixels, and the dot pixels on a die. Two pixels are connected only when they share an edge; touching at just a corner does not count.
A set of pixels is connected if, for every pair of pixels and in , there is a sequence of pixels in with , , and adjacent to for every .
- A die is a maximal connected set of non-background pixels (both die pixels and dot pixels count as non-background). "Maximal" means you cannot add any other non-background pixel without breaking the connectivity.
- A dot is a maximal connected set of dot pixels.
For every die in the image, determine how many dots it contains.
Input
The input contains several pictures. Each picture begins with a line holding two integers and , the width and the height of the picture, with .
The next lines contain exactly characters each:
.for a background pixel,*for a die pixel,Xfor a dot pixel.
Dice may have different sizes and, because of optical distortion, need not be perfectly square. Every picture contains at least one die, and each die shows between and dots, inclusive.
The input ends with a picture whose first line is 0 0; that picture must not be processed.
Output
Number the pictures in the order they appear.
For the -th picture, print a line Throw k, then on the next line print the number of dots on each die in that picture, sorted in increasing order and separated by single spaces.
Separate the output of consecutive pictures with one blank line. There is no blank line after the last picture.