Годинник | |
|
Graph3
|
|
Задача 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.
|
|
|
