Replicate Replicate Rfplicbte
시간 제한3초메모리 제한512 MB
각 단계마다 많아야 한 칸이 뒤집히는 홀수 패리티 셀룰러 오토마타의 최종 격자가 주어질 때, 유일한 최소 크기의 비어 있지 않은 초기 패턴을 구한다.
문제
자동 세포 제조 회사의 사장이 똑같은 부품을 대량 생산하는 공정을 새로 개발해 특허를 냈다. 이 공정은 각 칸이 비어 있거나 채워져 있는 2차원 격자를 쓴다. 세부 사항은 물론 영업 비밀이다.
먼저 복제하려는 부품 모양을 격자의 몇몇 칸에 채워 넣는다. 그다음 모든 칸이 동시에 상태를 바꾸는 갱신 단계를 반복한다. 한 칸의 다음 상태는 자기 자신과 이웃한 여덟 칸을 합한 아홉 칸으로 정해진다. 그중 채워진 칸이 홀수 개면 그 칸은 다음 단계에서 채워지고, 짝수 개면 비워진다. 그림 1은 채워진 칸 세 개짜리 간단한 모양이 복제되는 몇 단계를 보여 준다.
그림 1. 복제 과정.
그런데 공정에 결함이 생겼다. 갱신 단계가 하나 끝날 때마다 격자의 한 칸이 저절로 상태를 뒤집을 수 있다. 그림 2는 첫 번째 단계 뒤에 한 칸이, 세 번째 단계 뒤에 또 다른 한 칸이 뒤집혔을 때 일어날 수 있는 일을 보여 준다.
그림 2. 복제 과정에서 생긴 오류. 이 그림은 첫 번째 예제 입력에 해당한다.
원래 모양은 사라지고 복제가 끝난 결과만 남았다. 그 결과에는 오류가 섞여 있을 수 있다. 주어진 최종 모양을 만들어 낼 수 있는 가장 작은 시작 모양을 구하라. 시작 모양은 비어 있으면 안 된다. 갱신 단계는 0번 이상 진행되었고, 각 단계 뒤에 최대 한 칸이 저절로 뒤집혔다.
입력
첫 줄에 최종 모양을 감싸는 최소 직사각형의 너비 와 높이 가 주어진다 (, ).
다음 개 줄에는 각각 문자 개가 주어져 최종 모양을 나타낸다. 각 문자는 빈 칸을 뜻하는 '.' 또는 채워진 칸을 뜻하는 '#'이다. 첫 줄, 마지막 줄, 첫 열, 마지막 열에는 채워진 칸이 적어도 하나씩 있다.
출력
주어진 최종 모양을 만들어 낼 수 있는, 크기가 가장 작으면서 비어 있지 않은 시작 모양을 출력한다. 모양의 크기는 그 모양을 감싸는 최소 직사각형의 넓이다. 빈 칸은 '.', 채워진 칸은 '#'으로 쓰고, 필요한 최소한의 행과 열만 써서 출력한다. 조건을 만족하는 가장 작은 시작 모양은 하나뿐이다.