«Что за свинья прошла здесь - корова, что ли?»
Под дворцом царя Миноса размером NxM построен одноэтажный лабиринт размером NxMx1. Некоторые из кубов 1x1x1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.
К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1хS.
Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).
Напишите программу, вычисляющую это минимальное число разрезов.
Во входном файле записано сначала число N, затем число M, задающие размеры лабиринта (1N10, 1M10). Далее идет N строк, по M чисел в каждой, задающих лабиринт. Каждое из этих чисел 0 или 1 — 0 означает пустой куб, а 1 — гранитный.
В выходной файл выведите одно число — минимальное возможное количество разрезов, которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.
1 10 1 1 1 1 1 0 0 0 0 0
0
2 2 1 0 0 0
1
Задачи противовоздушной обороны: ...борьба с десантом на всем маршруте пролета,
уничтожение вертолетов огневой поддержки, действующих из засады»
Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более 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