시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB828828.571%

문제

민식이는 아래와 같은 두 가지 모양의 조각을 가지고 있다.

           A  A            BB
           AAAA

이 조각을 회전시키는 것은 불가능하다.

영식이는 '.'과 'X'로 이루어진 크기가 N×M인 격자를 가지고 있고, 격자의 각 칸은 '.'과 'X'로만 이루어져 있다. 격자의 한 칸은 조각의 문자 한 칸이 정확하게 들어가는 넓이이다. 민식이는 'X'가 되어있는 곳을 두 모양의 조각을 이용해 덮으려고 한다. 이때 조각을 겹치게 놓으면 안된다.

민식이가 'X'를 어떻게 가려야 하는지 구해보자.

입력

첫째 줄에 영식이의 종이의 세로 크기 N과 가로 크기 M이 주어진다. 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 격자의 정보가 주어진다. 격자의 정보는 첫 행부터 순서대로 주어지며, '.'와 'X'로만 이루어져 있다.

출력

N개의 줄에 민식이가 조각을 어떻게 덮어야 하는지 출력한다. 덮을 수 있는 방법이 여러 가지일 때는 사전순으로 가장 앞서는 것을 출력한다. (첫 줄이 같다면 둘째 줄을 비교하고, 그 다음 셋째 줄을 비교하고 이런 식으로) 불가능 한 경우에는 -1을 출력한다.

예제 입력 1

2 4
XXXX
XXXX

예제 출력 1

ABBA
AAAA

예제 입력 2

2 10
X..XXXX..X
XXXX..XXXX

예제 출력 2

A..ABBA..A
AAAA..AAAA

예제 입력 3

3 6
XXXXXX
XXXXXX
XXXXXX

예제 출력 3

ABBABB
AAAABB
BBBBBB

예제 입력 4

2 5
X..XX
XXXXX

예제 출력 4

-1

예제 입력 5

7 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXX..XXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

예제 출력 5

ABBAABBABB
AAAAAAAABB
ABBABBBBBB
AAAAA..ABB
ABBAAAAABB
AAAAABBABB
BBBBAAAABB

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013