The Die Is Cast
InterviewTime limit1sMemory limit128 MB
Read a pixel image, split non-background pixels into dice connected by shared edges, count the dot regions inside each die, and print the counts sorted.
- Level
Medium5 of 10
- Topics
- Graph, DFS, BFS, Implementation
- Solved
- No attempts yet
Problem
According to a usually reliable (but unnamed) source, a dangerous group has decided to let chance pick the moment of their move: they roll several dice, and the instant every die shows six dots on top is their signal to act.
The police can obtain a snapshot of the dice at any moment from nearby cameras, and they want a program that reads such a bitmap image and reports the outcome of the throw — that is, the number of dots visible on each die.
The input images use only three kinds of pixels: background, die body, and die dot. Two pixels are considered connected only if they share an edge; touching at a single corner is not enough. In the figure below, pixels A and B are connected, but B and C are not.

A set of pixels is connected if, for every pair of pixels , in , there is a sequence of pixels in with , , and every adjacent pair , connected.
Each maximal connected set of non-background pixels (die-body and dot pixels together) is a die: "maximal" means you cannot add any other non-background pixel without breaking connectivity. Likewise, each maximal connected set of dot pixels forms a single dot.
Input
The input contains pictures of several dice throws. Each picture starts with a line holding two integers and — the height and the width of the picture ().
The next lines contain characters each:
.— a background pixel,*— a die-body pixel,X— a die-dot pixel.
Every picture contains at least one die, and each die shows between and dots, inclusive. The number of dice is limited only by the picture size.
Dice and dots may have different sizes and need not be perfectly square, because of optical distortion; as long as each stays connected it may in fact have any shape. You may assume the dice are not "hollow": if every pixel outside the picture is treated as background, then all background pixels are connected.
The input ends with a picture whose first line is 0 0; that picture must not be processed.
Output
For each throw, print a single line: the text Throw:, then a space, then the numbers of dots on the dice in that picture, sorted in increasing order and separated by single spaces.