`Всеукраїнський центр проведення олімпіад в мережі Інтернет

Задача GRAPH3

(вновь предоставлена дизайнером фирмы "GraphSoft")

Картинка размером H на W пикселей, обертка для конфет "Сосиска в шоколаде" по-прежнему не придумывалась... На экране была все та же красная замкнутая линия толщиной в 1 пиксель. Творческий кризис прогрессировал... Ткнул я мышкой в точку внутри области, ограниченной красной линией -- появился одинокий синий пиксель. Я от нечего делать стал ставить синие точки, образующие сплошную линию, пока последняя из них не перекрасила красную точку. После этого, естественно, обертка не получилась... Вернув все в начальный вид, я повторил эти же действия для всех остальных точек внутри области, каждый раз возвращая в исходное состояние картинку после "перекрашивания" красной точки.

Сколько за это время я поставил синих точек, если каждый раз количество поставленных точек было минимальным? Для тех, кто не знаком с компьютерной графикой -пиксель имеет форму квадратика.

Ограничения:

1<H,W<=100.

Пиксели, составляющие цветную линию (кроме начального и конечного), имеют общие стороны ровно с двумя пикселями того же цвета.

Ввод/вывод:

Программа должна прочитать с клавиатуры: с первой строки - два числа H и W, а со следующих H строчек по W чисел. Красный пиксель обозначается единицей, белый - нулем. Программа должна вывести на экран число поставленных синих точек.

Пример:

Ввод> 6 7

Ввод> 0 0 1 1 1 0 0

Ввод> 0 1 1 0 1 1 1

Ввод> 0 1 0 0 0 0 1

Ввод> 0 1 0 0 0 0 1

Ввод> 0 1 1 1 1 1 1

Ввод> 0 0 0 0 0 0 0

Вывод> 19

В этом примере для 8 внутренних пикселей поставлено 2 точки и для одного - 3. Всего получилось 2*8+3=19.

 

© LIKT 1998-2024