그림 고치기 timer 2s memory - MB

검은색 점(문제에서는 '.'로 표시)와 흰색점(문제에서는 '#'로 표시)으로 이뤄진 그림이 있다.

문제에서 두개의 검은 점이 서로 상하좌우 위치로 인접해 있을 경우, 두개의 검은 점은 직접적으로 이어졌다고 정하자.

임의의 두개의 검은색 점 A와 B가 서로 연결 되어 있다는 것은, 다음과 같이 A와 B에 대한 경로가 존재해야 한다. A = P_0, P_1, ..., P_k = B, 여기서 P_i는 검은색 점을 뜻하며, P_i와 P_i+1은 직접적으로 두개의 검은색 점 P_i, P_i+1이 연결되어 있다는 것을 뜻한다.

블록이란 검은색 점들이 직접 혹은 간접으로 이어진 하나의 집합을 말한다.

아래 그림1 에서의 검은 점들은 모두 하나의 블럭에 속하며 그림2에서는 2개의 블럭(좌측 상단 사각형, 우측 하단 사각형)으로 나뉜다.

한 블록내에 속해 있는 모든 쌍에 대해서, 임의의 점의 쌍 A와 B에 대해 검은 점들을 거쳐서 이동하는 경로의 길이와 A와 B간의 맨하탄 거리의 값이 같을 경우 해당 블록은 '매끄럽다'고 한다.

여기서 점 A와 B의 맨하탄 거리라는 것은 각각 (xA, yA), (xB, yB)에 위치 해있을 경우, 각 좌표간의 차이의 합을 뜻한다.(|xA - xB| + |yA - yB|)

당신의 친구는 이메일로 모든 블럭이 매끄러운 그림을 보내왔다. 허나 마침 캠프에 와있던 당신은 캠프장의 인터넷의 상태가 말이 아니었기 때문에 몇 개의 검은 점들이 하얀색 점으로 바뀌어(기존의 하얀색 점은 여전히 하얀색점이다)있다. 최소한의 점들을 하얀색의 점을 검은색 점으로 바꿔서 원래 이미지를 복원하는 프로그램을 작성하라. 복원되는 이미지는 정확히 한 가지 경우만 존재한다.