Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более $$$5$$$). К сожалению, их нельзя ставить рядом — они друг для друга создают помехи. Каждый передатчик состоит из квадратных модулей, которые располагаются вплотную друг к другу.
Вам дана карта района, в котором расположена РЛС. Вся карта для удобства разбита на квадраты, и для каждого квадрата известно, располагается в нем какой-то из модулей одного из передатчиков РЛС или нет.
Требуется оградить забором (или несколькими заборами) минимально возможной суммарной длины все передатчики РЛС. Забор — это произвольная ломаная (ее элементы не обязаны идти по сторонам клеток). Одним забором могут быть огорожены сразу несколько передатчиков.
В первой строке заданы два целых числа $$$N$$$ и $$$M$$$ $$$(1 \leqslant N \leqslant 20; 1 \leqslant M \leqslant 20)$$$ — размеры района, в котором расположена РЛС.
Далее идет $$$N$$$ строк, по $$$M$$$ чисел в каждой, задающих карту района. Каждое из этих чисел $$$0$$$ или $$$1$$$ — $$$1$$$ означает, что в этом квадрате находится один из модулей передатчика РЛС, а $$$0$$$ — что в этом квадрате ничего ценного нет.
Общее количество передатчиков РЛС не превышает $$$5$$$. Каждый передатчик — это связанная группа модулей (модули называются связанными, если они располагаются в квадратах карты, у которых есть общая граница, либо связаны через какие-то другие модули). Ограничений на число модулей нет. Гарантируется, что на карте есть хотя бы один модуль.
Выведите одно число — минимально возможную длину забора.
Ваш ответ будет признан верным, если абсолютная или относительная погрешность ответа не превосходит $$$10^{-4}$$$.
9 100 0 0 0 0 0 0 0 0 00 0 0 1 1 1 0 0 0 00 0 0 1 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 1 0 0 0 0 1 1 1 01 0 0 0 0 0 0 0 0 00 0 0 0 0 0 1 0 0 0
26.892922227
3 30 0 00 1 00 0 0
4.000000000
В первом примере на рисунке РЛС состоит из $$$5$$$ передатчиков. Длина забора вокруг передатчика $$$1$$$ равна $$$9.236$$$. Передатчики $$$2$$$ и $$$3$$$ окружены общим забором длины $$$6.828$$$, и передатчики $$$4$$$ и $$$5$$$ окружены общим забором длины $$$10.828$$$.