문제 번호 5003 --소들의 아름다운 행렬(Cow Beauty Pageant)

5003: 소들의 아름다운 행렬(Cow Beauty Pageant)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 19  해결 문제 수: 7
[제출][채점상황][게시판][:]

문제 설명

최근의 가장 유명한 패션 트랜드는 검은 점을 2개 가지는 점박이 젖소이다.

패션 감각이 뛰어난 농부 존 두 개의 검 점을 가지는 점박이 젖소를 대량으로 사들였다.

하지만 불행히도 패션 트랜드는 너무나도 빨리 변하였다.

지금은 오직 한개의 검은 점을 가진 점박이 젖소의 인기가 높아졌다.

FJ는 그가 가진 젖소들의 점박이 무늬를 검은 페인트를 이용하여 하나로 만들고 싶어졌다.

젖소의 몸은 N*M( 1 <= N,M <= 50 ) 의 격자에 아래와 같은 문자들로 구성된다.

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....


여기서 "X"는 검은 점을 나타낸다. 이 "X"무늬가 상하좌우로 연결되어 있으면 하나의 큰 점을 의미한다. (단, 대각선은 연결되지 않은 것으로 본다.)

FJ의 젖소들은 모두 2개의 검은 점을 가진다.

FJ는 검은 페인트를 최소한으로 사용하여 이 2개의 점을 1개로 보이도록 하고 싶어한다. 예를 들어 위 그림의 소를 아래와 같이 3군데만 검은 페인트를 칠하면 점은 하나가 된다.

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....


젖소들의 몸의 점박이 정보를 이용하여 최소한의 페인트를 사용할 수 있도록 농부존을 도와주는 프로그램을 작성하시오.

입력

첫 번째 줄에 두 개의 정수 N, M이 공백으로 구분되어 입력된다.
2~N+1번째 줄까지 M개의 "X", "."으로 이루어진 문자열이 입력된다.

출력

두 점을 하나로 만들기 위한 최소한의 페인트 사용량을 출력한다.

입력예시

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

출력예시

3

도움말

출처

[제출][채점상황]