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

문제

세준이는 N*M크기의 그림을 그리려고 하는데 1*1크기의 정사각형마다 색을 다르게 칠한다. 세준이는 흰색과 검정색만을 이용하는데, 흰색을 . 검정색을 #이라고 한다.

만약 두 개의 검정색 칸이 서로 공통된 변을 공유하고 있다면, 두 칸은 직접 연결되어 있는 것이다. 두 개의 검정색 칸 A와 B가 간접적으로 연결되어 있다는 말은, A=P1 -> P2 -> ... -> Pk=B로 가는 경로가 있을 때 (Pi와 Pi+1은 직접 연결되어 있을 때) 간접적으로 연결되어 있다고 한다.

세준이의 그림에는 검정색 그룹이 몇 개 있는데, 그 그룹 속에 있는 모든 한 쌍의 검정색 칸은 직, 간접적으로 연결되어 있어야 한다. 다른 그룹과 연결되어 있는 것이 있으면 안 된다.

세준이의 그림에 존재하는 검정색 그룹의 특징은 그 그룹속의 모든 쌍의 경로의 길이가 그 쌍의 Manhattan Distance와 같다.

Manhattan Distance란 어떤 두 칸 A(Xa, Ya)와 B(Xb, Yb)가 있을 때, 두 칸의 거리는 |Xa-Xb| +|Ya-Yb|이다.

세준이가 그림을 다솜이에게 자랑을 하려고 보냈으나, 통신오류로 그림의 검정 칸중 일부가 흰색으로 변했다.

다솜이는 전송받은 그림을 고쳐서 원래 그림으로 만들려고 한다. 다솜이가 세준이의 그림의 특징을 지키면서 원래 그림으로 만들 때, 고쳐야 하는 칸의 회수를 최소로 하려고 한다.

다솜이가 고친 세준이의 원래 그림을 출력하는 프로그램을 작성하시오. 

입력

첫째 줄에 그림의 세로크기 N과 가로크기 M이 들어온다. 둘째 줄부터 N개의 줄에 그림이 들어온다. (1 ≤ N, M ≤ 50)

출력

세준이의 원래 그림을 첫째 줄부터 N개의 줄에 걸쳐 출력한다. 최소로 고치는 원래 그림은 유일하다.

예제 입력 1

6 8
###.####
#.#.#..#
.#...#.#
.#####.#
......#.
########

예제 출력 1

########
########
########
########
########
########

예제 입력 2

4 4
....
.##.
.##.
....

예제 출력 2

....
.##.
.##.
....

예제 입력 3

5 5
.....
.###.
.#.#.
.###.
.....

예제 출력 3

.....
.###.
.###.
.###.
.....

예제 입력 4

5 7
.......
.###...
.#..##.
.###.#.
.....#.

예제 출력 4

.......
.###...
.#####.
.#####.
.....#.

출처

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: dotorya