| Автор: | Кировская командная олимпиада 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 — гранитный.
В выходной файл выведите одно число — минимальное возможное количество разрезов, которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.
| № | Входной файл (d.in) |
Выходной файл (d.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|