HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming > problem:


Вирусы

Section problems

• Вирусы
• Гангстеры
• Phalanx

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Difficulty Alpha

На поле размером N*N расположено M вирусов. За каждый ход вирус заражает 4 соседние с ним клетки. Положение вирусов задано координатами на поле. Требуется написать программу, определяющую, за какое наименьшее количество ходов будет заражено все поле.

Ввод
В первой строке записаны два числа N (1 ≤ N ≤ 100) и M (1 ≤ M ≤ 10). Каждая из следующих M строк содержит по два числа - координаты вируса на поле. Все числа целые, координаты по величине не превосходят размеров поля. Левая нижняя клетка поля имеет координаты (1, 1).
Вывод
В первую и единственную строку выведите одно число - искомое наименьшее количество ходов.

Ввод 1 Ввод 2
2 1
2 1
58 4
46 22
20 26
38 30
23 37
Вывод 1 Вывод 2
2
48

Для отправки решений необходимо выполнить вход.

www.contester.ru