ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Задачи со всего света > задача:


Вирусы

Задачи сборника

• Бронзовый призёр
• Вирусы
• Забавная игра
• Максимум из минимумов
• Площадь пересечения
• Почтовые цифры
• Счастливые билеты
• Шашечная доска
• Прямоугольники
• Редкое имя

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Сложность Альфа

На поле размером 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