Задача D. Ковролин для минотавра

Автор:Кировская командная олимпиада 2001 года   Ограничение времени:8 сек
Входной файл:d.in   Ограничение памяти:64 Мб
Выходной файл:d.out  

Условие

Под дворцом царя Миноса размером N × M построен одноэтажный лабиринт размером N × M × 1. Некоторые из кубов 1 × 1 × 1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.

К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма "Минос, минотавр and Co" закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1 × S.

Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).

Напишите программу, вычисляющую это минимальное число разрезов.

Формат входного файла

Во входном файле записано сначала число N, затем число M, задающие размеры лабиринта. Далее идет N строк, по M чисел в каждой, задающих лабиринт. Каждое из этих чисел 0 или 1 — 0 означает пустой куб, а 1 — гранитный.

Формат выходного файла

В выходной файл выведите одно число — минимальное возможное количество разрезов, которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.

Ограничения

1 ≤ N ≤ 10, 1 ≤ M ≤ 10

Примеры тестов

Входной файл (d.in) Выходной файл (d.out)
1
1 10
1 0 0 0 0 0 0 0 0 1
0
2
2 5
0 0 0 0 0
0 1 1 1 0
2

0.337s 0.168s 13