Pejntbrasz

Limit pamięci: 32 MB

Karolek dostał na gwiazdkę komputer. Niestety nie doprecyzował w liście do Świętego Mikołaja, że do komputera przydałoby się dorzucić trochę gier, i w rezultacie musiał zadowolić się Saperem i Pasjansem. Jednak niedawno odkrył jeszcze jeden program, który okazał się o wiele ciekawszy niż dwie wspomniane gry.

Pejntbrasz (bo o nim mowa) jest prostym programem do rysowania. Umożliwia tworzenie prostokątnych czarno-białych rysunków. Rysunek o wymiarach składa się z kwadratowych pikseli. Karolkowi najbardziej spodobało się narzędzie do wypełniania kolorem. Zainspirowało go do wymyślenia nowej gry. Zasady są proste: mając dany czarno-biały rysunek, należy wykonując jak najmniej operacji wypełniania kolorem, spowodować by wszystkie piksele na obrazku miały ten sam kolor.

Karolek chciałby sprawdzić jak dobrze umie grać w swoją grę. Poprosił Cię o napisanie programu, który dla danego obrazka obliczy ile operacji potrzeba do zakończenia gry.

Bardzo szczegółowy opis działania narzędzia do wypełniania kolorem

Dwa piksele sąsiadują ze sobą, jeżeli mają wspólną krawędź. Dwa piksele , są połączone, jeśli istnieje ciąg pikseli tego samego koloru, taki że dla każdego piksele oraz sąsiadują ze sobą. Obszarem nazwiemy maksymalny zbiór pikseli połączonych. Aby użyć narzędzia do wypełniania koloru, zaznaczamy wybrany piksel na obrazku. W wyniku tej operacji wszystkie piksele z obszaru, do którego należał wybrany piksel, zmienią kolor.

Wejście

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite i , oznaczające wysokość i szerokość obrazka. Liczba piksli w obrazku nie przeznacza . Kolejne wierszy opisują obrazek. W każdym jest znaków ('.' oznacza biały piksel, natomiast 'X' oznacza piksel czarny).

Wyjście

W jedynym wierszu wyjścia należy wypisać minimalną liczbę operacji potrzebnych do zakończenia gry Karolka.

Przykład

Dla danych wejściowych:

4 7
..X.X.X
...XXX.
.X..XX.
.....XX

poprawną odpowiedzią jest:

2

Autor zadania: Tomasz Idziaszek (zapożyczenie).