Rings

Dee Siduous is a botanist who specializes in trees. A lot of her research has to do with the formation of tree rings, and what they say about the growing conditions over the tree's lifetime. She has a certain theory and wants to run some simulations to see if it holds up to the evidence gathered in the field.

One thing that needs to be done is to determine the expected number of rings given the outline of a tree. Dee has decided to model a cross section of a tree on a two-dimensional grid, with the interior of the tree represented by a closed polygon of grid squares. Given this set of squares, she assigns rings from the outer parts of the tree to the inner as follows: calling the nontree grid squares “ring 0”, each ring n is made up of all those grid squares that have at least one ring (n – 1) square as a neighbor (where neighboring squares are those that share an edge).

An example of this is shown in the figure below:

Most of Dee's models have been drawn on graph paper, and she has come to you to write a program to do this automatically for her. This way, she'll use less paper and save some… well, you know.

Input Specification

The input contains several test cases. Each test case will start with a line containing two positive integers n and m, specifying the number of rows and columns in the tree grid, where n, m ≤ 100. After this will be n rows containing m characters each. These characters will be either 'T', indicating a tree grid square, or '.'.

Output Specification

For each test case, output a grid with the ring numbers. If the number of rings is less than 10, use two characters for each grid square; otherwise, use three characters for each grid square. Right-justify all ring numbers in the grid squares, and use '.' to fill in the remaining characters.

If a row or column does not contain a ring number, it should still be output, filled entirely with '.'s.

Sample Input

1. 6 6
2. .TT...
3. TTTT..
4. TTTTT.
5. TTTTT.
6. TTTTTT
7. ..T...
8. 3 4
9. TT..
10. TT..
11. ....

download as text file

Output for Sample Input

1. ...1.1......
2. .1.2.2.1....
3. .1.2.3.2.1..
4. .1.2.3.2.1..
5. .1.1.2.1.1.1
6. .....1......
7. .1.1....
8. .1.1....
9. ........

download as text file