Problem E
Least Squares
Input: Standard Input
Output: Standard Output
Time Limit: 5 Seconds
You are given
an irregularly-shaped area on a grid that you must cover completely with
non-overlapping squares of various sizes.
Doing this optimally (with the fewest number of squares) is
difficult. Very
difficult. Way too difficult for
your limited intelligence. So I won't
ask. Why waste your time and mine?
Instead, your
much simpler task is merely to cover it with squares. That's it. Do you think you can handle
that? I have some crayons you can
use. (Squares will be "coloured" by filling them with capital letters, A to
Z)
Oh, make sure
that no touching squares have the same colour, so we
can tell them apart. (Touching means
sharing part of an edge; corners don't count)
Oh yes, and I'd appreciate it if you'd give me the lexicographically first configuration that satisfies this property. For simplicity's sake. (In other words, if every row of the solved grid is concatenated into one string, give me the solution whose string would come first in a dictionary)
Input
Every case
consists of a grid to fill with squares.
The first line will contain m (0 < m <= 100), the number of rows
in the grid, and n (0 < n <= 80), the number of columns. The remaining m lines will consist of a
drawing of the area. A
'?' represents a portion of the area to be filled, while a '.' represents a
boundary section of the grid that you should ignore.
There will be at most 100 cases. The last case will be followed by a line with two 0s.
For each case, output the desired coloured solution, in grid format. Separate the output of consecutive cases with a blank line.
5 5????.???.???????????????.0 0 |
AAAB. AAA.A AAABB BBCBB BBAC. |
Problemsetter:
Derek Kisman, Member of Elite Problemsetters' Panel