РЛС
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задачи противовоздушной обороны: ...борьба с десантом на всем маршруте пролета, уничтожение вертолетов огневой поддержки, действующих из засады

Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более $$$5$$$). К сожалению, их нельзя ставить рядом — они друг для друга создают помехи. Каждый передатчик состоит из квадратных модулей, которые располагаются вплотную друг к другу.

Вам дана карта района, в котором расположена РЛС. Вся карта для удобства разбита на квадраты, и для каждого квадрата известно, располагается в нем какой-то из модулей одного из передатчиков РЛС или нет.

Требуется оградить забором (или несколькими заборами) минимально возможной суммарной длины все передатчики РЛС. Забор — это произвольная ломаная (ее элементы не обязаны идти по сторонам клеток). Одним забором могут быть огорожены сразу несколько передатчиков.

Входные данные

В первой строке заданы два целых числа $$$N$$$ и $$$M$$$ $$$(1 \leqslant N \leqslant 20; 1 \leqslant M \leqslant 20)$$$ — размеры района, в котором расположена РЛС.

Далее идет $$$N$$$ строк, по $$$M$$$ чисел в каждой, задающих карту района. Каждое из этих чисел $$$0$$$ или $$$1$$$ — $$$1$$$ означает, что в этом квадрате находится один из модулей передатчика РЛС, а $$$0$$$ — что в этом квадрате ничего ценного нет.

Общее количество передатчиков РЛС не превышает $$$5$$$. Каждый передатчик — это связанная группа модулей (модули называются связанными, если они располагаются в квадратах карты, у которых есть общая граница, либо связаны через какие-то другие модули). Ограничений на число модулей нет. Гарантируется, что на карте есть хотя бы один модуль.

Выходные данные

Выведите одно число — минимально возможную длину забора.

Ваш ответ будет признан верным, если абсолютная или относительная погрешность ответа не превосходит $$$10^{-4}$$$.

Примеры

Входные данные
9 10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
Выходные данные
26.892922227
Входные данные
3 3
0 0 0
0 1 0
0 0 0
Выходные данные
4.000000000

Примечание

В первом примере на рисунке РЛС состоит из $$$5$$$ передатчиков. Длина забора вокруг передатчика $$$1$$$ равна $$$9.236$$$. Передатчики $$$2$$$ и $$$3$$$ окружены общим забором длины $$$6.828$$$, и передатчики $$$4$$$ и $$$5$$$ окружены общим забором длины $$$10.828$$$.