Задача №1134. РЛС
Задачи противовоздушной обороны: ...борьба с десантом на всем маршруте пролета,
уничтожение вертолетов огневой поддержки, действующих из засады»
Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более 5). К сожалению, их нельзя ставить рядом — они друг для друга создают помехи. Каждый передатчик состоит из квадратных модулей, которые располагаются вплотную друг к другу.
Вам дана карта района, в котором расположена РЛС. Вся карта для удобства разбита на квадраты, и для каждого квадрата известно, располагается в нем какой-то из модулей одного из передатчиков РЛС или нет.
Требуется оградить забором (или несколькими заборами) минимально возможной суммарной длины все передатчики РЛС. Забор — это произвольная ломаная (ее элементы не обязаны идти по сторонам клеток). Одним забором могут быть огорожены сразу несколько передатчиков.
Во входном файле записаны два числа N и M, задающие размеры района, в котором расположена РЛС (1N20, 1M20). Далее идет N строк, по M чисел в каждой, задающих карту района. Каждое из этих чисел 0 или 1 — 1 означает, что в этом квадрате находится один из модулей передатчика РЛС, а 0 — что в этом квадрате ничего ценного нет.
Общее количество передатчиков РЛС не превышает 5. Каждый передатчик — это связанная группа модулей (модули называются связанными, если они располагаются в квадратах карты, у которых есть общая граница, либо связаны через какие-то другие модули).
Ограничения на число модулей нет.
В выходной файл выведите одно число — минимально возможную длину забора с тремя значащими цифрами после точки.
2 2 1 0 0 1
6.828
4 5 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1
18.000