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