e-olymp
Задачі

Острови

Острови

prb78Аби не відставати від сучасної світової тенденції, уряд країни Олімпія планує побудувати декілька островів для залучення туристів. Карта островів вже підготовлена та являє собою таблицю розміром N x M клітинок. Кожна клітинка може бути водою або сушею. Набір клітинок, що представляють сушу, є островом, коли з будь-якої з них можна потрапити в будь-яку іншу, переміщуючись сусідніми по горизонталі або вертикалі клітинами, та не існує інших таких клітин поза набором.

Для зручності було вирішено побудувати мости між деякими островами так, щоб усі острови стали сполученими між собою. Мости повинні будуватися лише по вертикалі чи горизонталі, проходити лише по клітинах з водою, починатись та закінчуватися клітинами з сушею. За вартість будівництва моста можна вважати кількість клітин води, через яку він проходить. Треба знайти мінімальну можливу загальну вартість будівництва групи мостів, які б сполучали між собою усі острови. Іншими словами, щоб з кожної клітини суші можна було досягнути будь-якої іншої, переміщуючись до сусідніх по вертикалі та горизонталі клітин суші, або мостам. Два різні мости можуть перетинатися між собою, тобто проходити через одну й ту саму клітину води на різних рівнях.

Завдання

Напишіть програму, що за картою островів знаходить мінімальну вартість будівництва групи мостів, що з’єднують всі острови.

Вхідні дані

Перший рядок містить два цілих числа N та M (1 N, M 500) - розміри карти островів. Кожен з наступних N рядків містить M символів 0 (вода) або 1 (суша).

Вихідні дані

Вивести одне ціле число - знайдену мінімальну вартість будівництва мостів. Якщо сполучити острова мостами неможливо, вивести число -1.

Ліміт часу 0.3 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані
5 5
01110
00100
10010
00100
10001
Вихідні дані
8
Автор Шаміль Ягіяєв
Джерело 2008 XXI Всеукраїнська олімпіада з інформатики, Львів, Квітень 5 - 11, тур 1