cho.shresearchmini
ProblemCode
Description
Time limit
Memory limit
cho.shTime limit
Memory limit
Minsik has two kinds of pieces.
Piece A (2 rows by 4 columns):
A A
AAAA
Piece B (two horizontal cells):
BB
Neither piece may be rotated.
Youngsik has an N×M grid made up only of . and X. Each grid cell is exactly the size of one cell of a piece. Minsik wants to cover every cell marked X with the two pieces, leaving no X uncovered. Pieces may not overlap one another, and no piece may cover a . cell.
Find a way to cover all of the X cells.
The first line contains the grid height N and width M, separated by a space; both are natural numbers at most 50. Each of the next N lines contains one row of the grid as a length-M string consisting only of . and X.
Print the covered grid on N lines. Each cell covered by a piece is shown as that piece's letter (A or B), and every . cell stays .. If several coverings are possible, print the one that comes first in lexicographic order (if the first lines are equal, compare the second lines, then the third, and so on). If it is impossible to cover every X, print -1.