<ПРЕД Задача:
СЛЕД>
Задачу решили 107 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Камелот

Time limit = 5

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

Сначала фигуры короля и нескольких рыцарей располагаются в различных клетках доски размером NxN. Король может перемещаться на одну клетку в любом направлении.


Возможные перемещения короля
Рыцарь ходит буквой 'Г' (так же как конь в шахматах).

Возможные перемещения рыцаря

Во время игры можно поместить любое количество фигур на одной клетке.

За один ход игрок может перемещать только одну фигуру, но, если король находится в клетке, где есть рыцарь (рыцари), он может взять одного рыцаря и переместиться вместе с ним (ходом рыцаря) за один ход.

Необходимо за наименьшее число ходов собрать всех рыцарей и короля в одной клетке, чтобы они смогли в очередной раз отпраздновать свою дружбу.

Вход В первой строке: размер N (4 ≤ N ≤ 50) игрового поля и количество M (M ≤ 100) рыцарей. Во второй строке указываются координаты короля, а в следующих M строках — координаты рыцарей (координаты — это два натуальных числа из отрезка [1, N]).

Выход Минимальное количество ходов, которые нужно сделать чтобы собрать все фигуры в одной клетке.

Вход#1
8 4
4 4
1 3
1 8
8 1
8 8
Выход#1
10

Автор:
Андрей Уланов (идея взята из задания Курской областной олимпиады по информатике 2000 г.).
16 Мая 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 3.228.11.9