Problem 1: Cow Beauty Pageant (Silver Level) [Brian Dean]
Прослышав, что модно иметь коров с тремя пятнами, Фермер Джон купил целое стадо таких коров. К несчастью, мода меняется очень быстро, и сейчас в моде коровы с одним пятном.
ФД теперь хочет подкрасить своих коров так, чтобы они стали с одним пятном. Раскраска коровы задается двумерным массивом символов (N*M), например, так:
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... ..XXX....XXX....
Здесь 'X' обозначает часть пятна. Два символа 'X' принадлежат одному и тому же пятну, если они соседние вертикально или горизонтально (диагональные соседними не являются). Все коровы ФДЖ имеют ровно 3 пятна.
ФД хочет потратить как можно меньше краски, чтобы объединить три пятна в одно. На примере выше, он может сделать это, покрасив только 4 позиции, они обозначены символом ‘*’ на рис. ниже.
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ...*....XXXXX... ..XXX....XXX....
Помогите ФД определить минимальное количество клеток(символов), которые нужно закрасить, чтобы объединить три пятна в одно.
PROBLEM NAME: pageant
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M (1 <= N,M <= 50).
* Строки 2..1+N: Каждая содержит строку из M символов 'X' и '.', указывающих соответствующую линию раскраски коровы.
Формат выходных данных
* Line 1: Минимальное количество сиволов 'X', которые нужно добавить ко введенным данным, чтобы получить единое пятно.
Примечание
4 символа ‘X’ нужно добавить, чтобы получить одно пятно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....
|
4
|