Задача Space
Орбітальна станція являє собою куб розмірами n*n*n, що розділений
переборками на одиничні відсіки. Кожна переборка має люк. Між деякими
парами відсіків є прямий зв'язок (телепорт), а
деякі відсіки завантажені приладами, причому телпортів
такі відсіки не мають .Космотнавт знаходиться
в одному з вільних відсіків і бажає перейти в інший вільний відсік.
Яку мінімальну кількість люків він має пройти для цього,
не заходячи в жоден з відсіків, що
завантаженіі приладами? Вважається, що при телепортації космонавт не проходить
ні через один люк.
Технічні умови
Ви вводите з клавіатури розмір станції n (1<=n<=50), кількість телепортів
K, кількість загромаджених відсіків L,
(0<=K,L<=500), потім K груп по 6 чисел -
координати відсіків, з'єднаних телепортом, потім
L груп по 3 числа - координати зайнятих відсіків, потім координати космонавта та координати відсіку,
куди він направляється. Всі дані вводяться через пропуск в одну стрічку.
Ви виводите на екран шукану мінімальну кількість люків, якщо космонавт потрапити
у заданий відсік не зможе, виводить -1.
Приклад
Введення 5 2 6 1 3 3 2 3 2 4 4 4 1 4 3 4 1 1 3 5 4 1 2 4 5 3 2 5 5 5 2 4 1 2 4 2 5 5 4
Виведення 4
Задача Space
Орбитальная станция представляет собой куб размером
n*n*n, раздeлеленный переборками на единичные отсеки.
В каждой переборке имеется люк. Между некоторыми парами отсеков
имеется прямое сообщение (телепорт), а некоторые отсеки заняты
приборами, при этом загруженые отсеки не имеют
телепортов. Космонавт находится в одном из свободных отсеков и хочет
перейти в другой свободный отсек. Какое минимальное
количество люков он должен пройти для этого, не заходя ни
в один отсек, занятый приборами? Считается, что при телепортировании
космонавт не проходит ни одного люка.
Технические условия
Программа читает с клавиатуры размер станции
n (1<=n<=50), количество телепортов K
, количество занятых отсеков L (0<=K,L<=500), затем
K групп по 6 чисел - координаты отсеков, соединенных телепортом,
затем L групп по 3 числа - координаты занятых
отсеков, затем координаты космонавта и координаты отсека,
куда космонавт направляется. Все данные вводятся через
пробел в одну строку.
Программа выводит на экран искомое минимальное количество люков, если
космонавт попасть в заданный отсек не сможет,
выводит -1.
Пример
Ввод 5 2 6 1 3 3 2 3 2 4 4 4 1 4 3 4 1 1 3 5 4 1 2 4 5 3 2 5 5 5 2 4 1 2 4 2 5 5 4
Вывод 4