e-olymp 74. Паук и муха — 2

Задача

В пустой прямоугольной комнате длины [latex]А[/latex], ширины [latex]В[/latex] и высоты [latex]С[/latex] муха упала на пол и уснула. Паук, находящийся на одной из стен, или на полу, или на потолке, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится? Известно, что паук может передвигаться только по поверхности комнаты или же спускаться на паутине с потолка на пол, но только под прямым углом.

Входные данные

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке – координаты мухи на полу [latex]X1[/latex], [latex]Y1[/latex], [latex](0 ≤ X1 ≤ A[/latex], [latex]0 ≤ Y1 ≤ B)[/latex]. В третьей строке – координаты паука [latex]X2[/latex], [latex]Y2[/latex], [latex]Z2[/latex], [latex](0 ≤ X2 ≤ A[/latex], [latex]0 ≤ Y2 ≤ B[/latex], [latex]0 ≤ Z2 ≤ C)[/latex]. Все входные данные – целые не отрицательные числа, не превосходящие [latex]500[/latex].

Выходные данные

Одно число – расстояние, на которое переместится паук, посчитанное с точностью до 2-х знаков после запятой.

Тесты

Входные данные Выходные данные
[latex]A[/latex] [latex]B[/latex] [latex]C[/latex] [latex]X1[/latex] [latex]Y1[/latex] [latex]X2[/latex] [latex]Y2[/latex] [latex]Z2[/latex] [latex]S[/latex]
[latex]4[/latex] [latex]7[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]8.06[/latex]
[latex]145[/latex] [latex]26[/latex] [latex]306[/latex] [latex]12[/latex] [latex]24[/latex] [latex]0[/latex] [latex]0[/latex] [latex]305[/latex] [latex]309.34[/latex]
[latex]26[/latex] [latex]18[/latex] [latex]53[/latex] [latex]24[/latex] [latex]15[/latex] [latex]24[/latex] [latex]1[/latex] [latex]53[/latex] [latex]58.52[/latex]
[latex]89[/latex] [latex]89[/latex] [latex]189[/latex] [latex]12[/latex] [latex]24[/latex] [latex]0[/latex] [latex]89[/latex] [latex]16[/latex] [latex]70.77[/latex]
[latex]18[/latex] [latex]26[/latex] [latex]145[/latex] [latex]14[/latex] [latex]2[/latex] [latex]17[/latex] [latex]26[/latex] [latex]141[/latex] [latex]147.14[/latex]

Код программы

Решение задачи

Данная задача решается с помощью «разверток» комнаты: переход от трёхмерного пространства к двумерному.
Вид комнаты:

Рассмотрим такие случаи:

  1. Паук находится на полу ([latex]Z_2 = 0[/latex]);
  2. Паук находится на одной из стенок ([latex]X_2 = 0[/latex], или [latex]X_2 = A[/latex], или [latex]Y_2 = 0[/latex], или [latex]Y_2 = B[/latex] и [latex]Z_2 \neq 0[/latex]) либо на потолке ([latex]X_2 \neq 0[/latex], и [latex]X_2 \neq A[/latex], и [latex]Y_2 \neq 0[/latex], и [latex]Y_2 \neq B[/latex], и [latex]Z_2 = C[/latex]).

Первый случай тривиален и вычисляется по формуле [latex]\sqrt{(X_1 — X_2)^2 + (Y_1 — Y_2)^2}[/latex] с помощью функции [latex]distance[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

  • Паук ползет по этой стенке, затем по полу. Тогда развертка будет такой:
  • Паук ползет через ближнюю к нам стенку и по полу. Тогда развертка следующая:
  • Аналогичен предыдущему случаю, только через дальнюю от нас стенку.

По этим разверткам мы можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex]. Если же паук находится в одном из углов комнаты, то мы находим наименьшее расстояние из двух вариантов развертки.
Когда же паук сидит на потолке, не соприкасаясь ни с одной из стенок, у него есть 13 вариантов:

  • Паук спускается с потолка на паутине, затем ползет точно так же, как и в самом первом случае.
  • Паук ползет по потолку, по одной из стенок и по полу. Тогда развертка будет выглядеть следующим образом (потолок можно развернуть в 4 стороны — отсюда 4 случая):
  • Паук ползет по потолку, а затем по двум соседним стенкам и по полу. Таких случаев 8, поскольку порядок следования стенок, по которым тот ползет, также важен. Развертка одного из них:

По этим разверткам мы также можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex].

Ссылки

Условие задачи на e-olymp
Задача Дьюдени о пауке и мухе
Код решения

e-olymp 4853. Кратчайший путь

Задан неориентированный граф. Найдите кратчайший путь от вершины a до вершины b.

Условие задачи на e-olimp.
Cсылка на пройденный тесты.

Раз нам надо найти кратчайший путь путь, то будем использовать BFS- поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства я использовал вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор «graf», выступающий в роли графа, причем мы добавляем сразу к вершинам ([latex] graf[x].push_back(y);[/latex]) то есть [latex] x[/latex] — ая вершина получает связь с вершиной [latex] y[/latex], и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем — нибудь, если да, что работаем [latex] while [/latex] — ом, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция [latex] bfs[/latex] вернет [latex] 1[/latex], что запустит тело [latex] if [/latex]- а и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор [latex] family[/latex], в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла [latex] i [/latex] -ая вершина). Восстановленный путь записываем в вектор [latex] ans[/latex]. После чего [latex] while[/latex] прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим [latex]-1[/latex], иначе выводим количество вершин, участвующих в построении пути и сам путь.

link.