가리기
시간 제한2초메모리 제한128 MB
회전 없이 6칸 A조각과 가로 2칸 B조각만으로 그리드의 모든 X칸을 겹치지 않게 덮어, 사전순으로 가장 작은 배치를 출력하거나 불가능하면 -1을 출력합니다.
문제
민식이는 다음과 같은 두 종류의 조각을 가지고 있다.
조각 A (2행 4열):
A A
AAAA
조각 B (가로 2칸):
BB
두 조각은 회전할 수 없다.
영식이는 .과 X로만 이루어진 N×M 격자를 가지고 있다. 격자의 한 칸은 조각의 한 칸이 정확히 들어가는 크기이다. 민식이는 X로 표시된 모든 칸을 두 조각으로 빈틈없이 덮으려고 한다. 조각끼리 겹쳐서는 안 되고, . 칸을 덮어서도 안 된다.
X 칸을 모두 덮는 방법을 구하여라.
입력
첫째 줄에 격자의 세로 크기 N과 가로 크기 M이 공백으로 구분되어 주어진다. 두 값 모두 50 이하의 자연수이다. 둘째 줄부터 N개의 줄에 걸쳐 격자의 각 행이 주어지며, 각 행은 .과 X로만 이루어진 길이 M의 문자열이다.
출력
조각으로 덮은 결과를 N개의 줄에 출력한다. 각 조각이 덮은 칸은 그 조각의 문자(A 또는 B)로, . 칸은 그대로 .으로 표시한다. 덮는 방법이 여러 가지이면 사전순으로 가장 앞서는 것을 출력한다(첫째 줄이 같으면 둘째 줄을, 그다음 셋째 줄을 비교하는 식이다). 모든 X를 덮는 것이 불가능하면 -1을 출력한다.