## DMOPC '22 Contest 5 P5 - Twos and Threes

View as PDF

Points: 25
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Alice is playing a game of Twos and Threes. Twos and Threes is a one-player game played on a two-dimensional board containing a region to be covered. Alice has an infinite collection of dominoes and triominoes, i.e. tiles of the following shapes:

Alice can place her tiles on the board in any location and orientation. She wins the game if she finds a tiling of the region on the board such that all squares in the region are covered, all squares not in the region are not covered, and no two tiles overlap. Your task is to help Alice find a winning tiling of the region, or determine that the game cannot be won.

#### Input Specification

The first line of input contains two integers and .

The next lines each contain characters which are either # or ., representing squares that are in the region and squares that are not in the region, respectively.

#### Output Specification

If it is impossible to win the game, output IMPOSSIBLE.

Otherwise, output lines each consisting of characters which are either . or any letter from A to Z, representing a winning tiling of the region. Adjacent letters which are the same should represent squares that are covered by the same tile. You may use the same letter to represent different tiles, as long as those tiles do not cover orthogonally adjacent squares.

#### Sample Input

4 7
.#...##
.####.#
..#...#
####.##

#### Sample Output

.A...CC
.ABBB.C
..A...B
CCAA.BB

#### Explanation for Sample

The sample output corresponds to the following tiling: