|
Формула 001
(Время: 2 сек. Память: 32 Мб Сложность: 57%)
Мальчик Миша собирается участвовать в школьных соревнованиях по гонкам с препятствиями по версии «Формула 001». Но к любым соревнованиям необходимо готовиться. Младший брат Миши, Ральф, не так силен в гонках с препятствиями, как его старший брат, но зато он обладает незаурядной фантазией. Он решил помочь брату и придумал игру, играя в которую, можно существенно увеличить свой опыт в вождении гоночного автомобиля.
Игра состоит в следующем. Пусть у нас есть бесконечное игровое поле, покрытое бесконечной квадратной сеткой. Некоторое множество узлов этой сетки отмечено. Назовем это множество S. В игре участвуют несколько игроков. У каждого игрока есть машина – фигура, которая может находиться только в узлах из множества S. В начале игры все машины находятся в различных начальных узлах. Ход каждого игрока состоит в перемещении машины в некоторый узел из множества S, возможно, тот же самый. Цель игры – добраться до определенного, финишного узла первым.
Ход происходит по следующим правилам. Пусть на предыдущем шаге машина была перемещена на вектор (X, Y) (если это первый шаг, то X=0 и Y=0). Тогда за один текущий ход машину можно передвинуть на один из следующих векторов: (X−1, Y−1), (X−1, Y), (X−1, Y+1), (X, Y−1), (X, Y), (X, Y+1), (X+1, Y−1), (X+1, Y) и (X+1, Y+1).
Конечно, на какой-либо из этих векторов машину переместить можно только при том условии, что после этого она попадет в узел из множества S. Если ход сделать нельзя, то игрок считается проигравшим и выбывает из игры.
Некоторое время поиграв в эту игру, Миша и Ральф занялись ее анализом. В данный момент они хотят узнать, за какое наименьшее число ходов из стартового узла возможно попасть в финишный. Сами они эту задачу решить не смогли и обратились за помощью к Вам. Помогите им!
Входные данные
В первой строке входного файла INPUT.TXT находится N – число элементов множества S. 2 ≤ N ≤ 1000. В последующих N строках находятся координаты узлов из этого множества – целые числа Xi, Yi (−109 ≤ Xi, Yi ≤ 109).
Никакие два узла во входном файле не совпадают. Занумеруем эти узлы, начиная с 1, в порядке их описания во входном файле. Стартовым узлом будет являться узел с номером 1, финишным узел с номером N .
Выходные данные
В выходной файл OUTPUT.TXT выведите -1, если добраться до финишного узла невозможно. Иначе, в первой строке выведите минимальное требуемое число ходов K . Во второй выведите K+1 число – номера посещенных узлов в порядке посещения. Первым узлом должен быть узел с номером 1, последним – узел с номером N .
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
0 0
0 1
0 2 | 2
1 2 3 |
| 2 | 3
0 0
0 2
0 3 | -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
