폴리오미노

시간 제한2초메모리 제한128 MB

요약
X가 연속된 각 구간을 2칸짜리 BB와 4칸짜리 AAAA 블록으로 채워 사전순으로 가장 작은 보드를 출력하고, 홀수 길이 구간이 있으면 -1을 출력합니다.
난이도

보통10점 중 4점

유형
그리디, 문자열, 수학, 구현
정답자
아직 제출이 없습니다

문제

민식이는 AAAA와 BB 모양의 폴리오미노를 각각 무한히 가지고 있다.

.와 X로 이루어진 보드판이 주어진다. 모든 X는 서로 겹치지 않게 폴리오미노로 덮어야 하며, .는 폴리오미노로 덮을 수 없다.

조건을 만족하도록 보드판을 덮은 결과를 출력하라.

입력

첫째 줄에 보드판이 주어진다. 보드판의 길이는 최대 50이다.

출력

첫째 줄에 사전순으로 가장 앞서는 결과를 출력한다. 모든 X를 덮을 수 없다면 -1을 출력한다.

예제5

  1. 예제 1

    입력
    XXXXXX
    예상 출력
    AAAABB

  2. 예제 2

    입력
    XX.XX
    예상 출력
    BB.BB

  3. 예제 3

    입력
    XXXX....XXX.....XX
    예상 출력
    -1

  4. 예제 4

    입력
    X
    예상 출력
    -1

  5. 예제 5

    입력
    XX.XXXXXXXXXX..XXXXXXXX...XXXXXX
    예상 출력
    BB.AAAAAAAABB..AAAAAAAA...AAAABB