Задача
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.