Frankfurt UAS Programming Day

Start

2018-06-12 10:00 UTC

Frankfurt UAS Programming Day

End

2018-06-12 15:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -368 days 10:29:26

Time elapsed

5:00:00

Time remaining

0:00:00

Problem L
Polyomino Powers

/problems/polyomino/file/statement/en/img-0001.jpg
A polyomino is a polyform with the square as its base form. It is a connected shape formed as the union of one or more identical squares in distinct locations on the plane, taken from the regular square tiling, such that every square can be connected to every other square through a sequence of shared edges (i.e., shapes connected only through shared corners of squares are not permitted).
The most well-known polyominos are the seven tetrominos made out of four squares (see figure), famous from the Tetris® game, and of course the single domino consisting of two squares from the game with the same name. Some polyomino can be obtained by gluing several copies of the same smaller polyomino translated (but not rotated or mirrored) to different locations in the plane. We call those polyomino powers.

Input

One line with two positive integers $h, w \leq 10$. Next follows an $h \times w$ matrix of characters ‘.’ or ‘X’, the ‘X’s describing a polyomino and ‘.’ space.

Output

A $k$-power with $2 \leq k \leq 5$ copies of a smaller polyomino: Output a $h\times w$ matrix on the same format as the input with the ‘X’s replaced by the numbers $1$ through $k$ in any order identifying the factor pieces. Furthermore, if multiple solutions exist, any will do. Otherwise, output “No solution” if no solution exists.

Sample Input 1 Sample Output 1
3 7
.XXXXX.
.XX..X.
XXXX...
No solution
Sample Input 2 Sample Output 2
1 3
XXX
123
Sample Input 3 Sample Output 3
4 9
.X..X.X.X
.XX.X.X.X
XXXXXXXXX
.XX......
.1..2.3.4
.15.2.3.4
115223344
.55......