아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

두 개의 직사각형

면접 대비

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

요약
검은 칸과 흰 칸으로 이루어진 격자가 주어질 때, 검은 칸이 겹치지 않는 두 개의 직사각형으로 이루어져 있는지 판별하고, 가능하면 각각을 'a'와 'b'로 표시한다.
난이도

보통10점 중 6점

유형
구현, 완전 탐색, 배열, 기하
정답자
아직 제출이 없습니다

문제

한 유명한 추상 화가가 새 걸작 <<두 개의 검은 겹치지 않는 직사각형>>을 세상에 내놓았다. 그림은 m×nm\times n 직사각형을 1×11\times 1 정사각형으로 나눈 것이며, 그중 일부는 작가가 가장 좋아하는 색인 검은색으로 칠해져 있다. Fedya는 추상화를 좋아하지 않지만, 그림에 정말로 겹치지 않는 두 직사각형이 그려져 있는지 궁금해졌다. 그가 알아낼 수 있도록 도와주자. 직사각형이 겹치지 않는다는 것은 두 직사각형이 공통된 칸을 가지지 않는다는 뜻이다.

입력

첫째 줄에는 mm과 nn이 주어진다 (1≤m,n≤2001 \le m, n \le 200). 다음 mm개 줄에는 그림의 묘사가 주어진다. 각 줄은 정확히 nn개의 문자를 포함한다. 문자 <<.>>는 빈 칸을, 문자 <<#>>는 칠해진 칸을 나타낸다.

출력

그림을 겹치지 않는 두 직사각형으로 나타낼 수 있다면 첫째 줄에 <<YES>>를 출력하고, 다음 mm개 줄에는 입력 파일에 주어진 것과 같은 형태로 그림을 출력하되 첫 번째 직사각형에 해당하는 칸을 문자 <<a>>로, 두 번째 직사각형에 해당하는 칸을 문자 <<b>>로 바꾼다. 해가 여러 개라면 아무거나 출력한다.

나타낼 수 없다면 출력 파일에 <<NO>>를 출력한다.

예제5

  1. 예제 1

    입력
    4 6
    .###..
    .###..
    ...##.
    ......
    
    예상 출력
    YES
    .aaa..
    .aaa..
    ...bb.
    ......
    
  2. 예제 2

    입력
    3 6
    .###..
    .####.
    ..###.
    
    예상 출력
    NO
    
  3. 예제 3

    입력
    4 5
    .####
    .####
    .####
    .....
    
    예상 출력
    YES
    .abbb
    .abbb
    .abbb
    .....
    
  4. 예제 4

    입력
    3 3
    ...
    .#.
    ...
    
    예상 출력
    NO
    
  5. 예제 5

    입력
    3 3
    ...
    #.#
    ..#
    
    예상 출력
    YES
    ...
    b.a
    ..a