The die is cast

Interview

Time limit1sMemory limit128 MB

Summary
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 SS of pixels is connected if, for every pair of pixels aa and bb in SS, there is a sequence a1,a2,…,aka_1, a_2, \dots, a_k of pixels in SS with a=a1a = a_1, b=akb = a_k, and aia_i adjacent to ai+1a_{i+1} for every 1≤i<k1 \le i < k.

  • 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 ww and hh, the width and the height of the picture, with 5≤w,h≤505 \le w, h \le 50.

The next hh lines contain exactly ww characters each:

  • . for a background pixel,
  • * for a die pixel,
  • X for 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 11 and 66 dots, inclusive.

The input ends with a picture whose first line is 0 0; that picture must not be processed.

Output

Number the pictures 1,2,3,…1, 2, 3, \dots in the order they appear.

For the kk-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.

Examples1

  1. Example 1

    Input
    30 15
    ..............................
    ..............................
    ...............*..............
    ...*****......****............
    ...*X***.....**X***...........
    ...*****....***X**............
    ...***X*.....****.............
    ...*****.......*..............
    ..............................
    ........***........******.....
    .......**X****.....*X**X*.....
    ......*******......******.....
    .....****X**.......*X**X*.....
    ........***........******.....
    ..............................
    0 0
    
    Expected output
    Throw 1
    1 2 2 4