Under construction

Still being built. Things may change

The Die Is Cast

Interview

Time limit1sMemory limit128 MB

Summary
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 SS of pixels is connected if, for every pair of pixels aa, bb in SS, there is a sequence a1,a2,…,aka_1, a_2, \ldots, a_k of pixels in SS with a=a1a = a_1, b=akb = a_k, and every adjacent pair aia_i, ai+1a_{i+1} 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 HH and WW — the height and the width of the picture (1≤W,H≤5001 \le W, H \le 500).

The next HH lines contain WW 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 11 and 66 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.

Examples3

  1. Example 1

    Input
    15 30
    ..............................
    ................*.............
    ...*****.......****...........
    ...*X***......**X***..........
    ...*****.....***X**...........
    ...***X*......****............
    ...*****........*.............
    ..............................
    ..............................
    .....***.........******.......
    ....**X****......*X**X*.......
    ...*******.......******.......
    ..****X**........*X**X*.......
    .....***.........******.......
    ..............................
    3 3
    ...
    XXX
    ...
    0 0
    
    Expected output
    Throw: 1 2 2 4
    Throw: 1
    
  2. Example 2

    Input
    3 3
    ***
    *X*
    ***
    0 0
    
    Expected output
    Throw: 1
    
  3. Example 3

    Input
    5 7
    *******
    *X*X*X*
    *******
    *X*X*X*
    *******
    0 0
    
    Expected output
    Throw: 6