소 미인 대회 (브론즈)

최신 유행이 가죽에 반점이 두 개 있는 소라는 소식을 듣고, 농부 존(Farmer John)은 반점이 두 개인 소들로 이루어진 무리를 통째로 사들였다. 안타깝게도 유행은 빠르게 변하기 마련이라, 지금 가장 인기 있는 유행은 반점이 하나뿐인 소이다!

FJ는 각 소에 페인트를 칠해 두 반점을 하나로 합치는 방식으로 소들을 더 유행에 맞게 만들고 싶어 한다. 소의 가죽은 다음과 같은 N x M (1 <= N,M <= 50) 문자 격자로 표현된다.

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

여기서 각 'X'는 반점의 일부를 나타낸다. 두 'X'가 상하좌우로 인접하면(대각선 인접은 세지 않는다) 같은 반점에 속하므로, 위 그림에는 정확히 두 개의 반점이 있다. FJ의 무리에 속한 모든 소는 정확히 두 개의 반점을 가지고 있다.

FJ는 가능한 한 적은 페인트를 사용해 두 반점을 하나로 합치고 싶어 한다. 위 예시에서는 세 개의 문자에만 'X'를 추가로 칠하면 된다 (아래에서 새로 칠한 문자는 알아보기 쉽도록 '*'로 표시했다).

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

두 반점을 하나의 큰 반점으로 합치기 위해 FJ가 새로 칠해야 하는 'X'의 최소 개수를 구하시오.

첫째 줄: 공백으로 구분된 두 정수 N과 M.

둘째 줄부터 1+N번째 줄까지: 각 줄에 소 가죽 무늬의 한 행을 나타내는, 'X'와 '.'로 이루어진 길이 M의 문자열이 주어진다.

입력 무늬를 하나의 반점으로 만들기 위해 추가해야 하는 새로운 'X'의 최소 개수.

riseoj 작성

출처 올림피아드 > USACO > 2011-2012 > November > Bronze