그림 복원
시간 제한2초메모리 제한128 MB
일부 검은 칸이 하얀 칸으로 손상된 격자에서, 각 검은 그룹이 행과 열 모두 볼록하게 연결되도록 최소 개수의 칸만 다시 검은색으로 복원합니다.
문제
N x M 크기의 그림이 있다. 각 칸은 흰색 또는 검은색이며, 흰색은 ., 검은색은 #로 나타낸다.
두 검은색 칸이 한 변을 공유하면 직접 연결되어 있다고 한다. 두 검은색 칸 A와 B 사이에 A = P1, P2, ..., Pk = B인 검은색 칸들의 경로가 있고, 모든 Pi와 Pi+1이 직접 연결되어 있으면 두 칸은 간접적으로 연결되어 있다고 한다.
하나의 검은색 그룹은 서로 직접 또는 간접적으로 연결된 검은색 칸들의 집합이다. 서로 다른 그룹끼리는 연결되어 있지 않아야 한다.
원래 그림의 각 검은색 그룹은 다음 성질을 만족한다. 같은 그룹에 속한 임의의 두 검은색 칸 사이에는, 그룹 안의 검은색 칸만 지나면서 길이가 두 칸의 Manhattan distance와 같은 경로가 존재한다.
두 칸 A(Xa, Ya), B(Xb, Yb)의 Manhattan distance는 |Xa - Xb| + |Ya - Yb|이다.
그림을 전송하는 동안 일부 검은색 칸이 흰색으로 바뀌었다. 흰색 칸이 검은색으로 바뀌는 오류는 없다.
받은 그림에서 몇 개의 흰색 칸을 검은색으로 고쳐 원래 그림의 성질을 만족하게 하려고 한다. 고치는 칸 수를 최소로 했을 때의 그림을 출력하라.
입력
첫째 줄에 그림의 세로 크기 N과 가로 크기 M이 주어진다.
둘째 줄부터 N개의 줄에 받은 그림이 주어진다. 각 줄은 길이 M의 문자열이며 .과 #로만 이루어져 있다.
1 <= N, M <= 50
출력
고치는 칸 수가 최소가 되도록 복원한 그림을 첫째 줄부터 N개의 줄에 걸쳐 출력한다.
최소로 복원한 그림은 유일하다.