Задача Сhannels. Фермер Василий решил соединить свои три пруда каналами. У Василия есть карта его владений, которая задается двухмерным массивом символов (N*M), где символ 'X' помечает клеточку, которая принадлежит пруду. К тому же два символа 'X' принадлежат одному и тому же пруду, если они являются соседними по вертикали или горизонтали (клеточки по диагонали не являются соседними). Рассмотрим пример:
...............
..XXXX....XXX..
..XXXXX.....X..
..XX.......XXX.
........XXXXX..
.ХXXX....XXX...
С целью экономии Василий хочет построить каналы суммарно минимальной длины. В вышеприведенном примере, ему выгодно построить в 4 клеточках, они обозначены символом '*' на рис. ниже.
...............
..XXXX....XXX..
..XXXXX.....X..
..XX..*....XXX.
..*...**XXXXX..
.ХXXX....XXX...
Помогите Василию определить минимальную суммарную длину каналов.
Технические условия. Программа Сhannels читает с устройства стандартного ввода два целых числа в первой строке N, а во второй M (1 ≤ N, M ≤ 50). Следующие N строк описывают карту. Каждая строка содержит строку из M символов “X” либо “.”. Гарантируется, что во входных данных всегда 3 пруда. Программа выводит на устройство стандартного вывода единственное число – искомую величину.
Пример
|
Ввод |
Вывод |
|
6 15 ............... ..XXXX....XXX.. ..XXXXX.....X.. ..XX.......XXX. ........XXXXX.. .ХXXX....XXX... |
4 |