Informatica Online Judge

  Cow Beauty Pageant [0467 / 01D3]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 90   Total Tried : 74


The Champion of this Problem (C++) : gs13024 - 0ms / 1189byte
My Best Submission (C++) : N/A

[]

Background

최근의 가장 유명한 패션 트랜드는 검은 점을 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....



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

Input

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

Output

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

IO Example

입력
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....


출력
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]