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