Задача HilbertMaze о Codility

Question

Кто-нибудь может дать мне подсказку о том, как подойти к следующей задаче из Codility: https://codility.com/programmers/task/hilbert_maze/

Я мог бы найти кратчайший путь, генерируя лабиринт и ища кратчайший путь, используя BFS, но, поскольку ожидается, что сложность времени наихудшего случая будет O(N), я не думаю, что это был бы правильный способ идти. Временная сложность BFS равна O(|V| + |E]), где V - количество вершин, а E - количество ребер. Например, если N = 3, у нас есть сетка размером 17x17, и интуитивно очевидно, что мы не можем найти путь только за 3 шага.

Таким образом, либо указанная временная сложность неверна и должна быть чем-то вроде M^2, либо есть простой способ просто вычислить расстояние между двумя точками без использования графовых алгоритмов. Я нашел несколько алгоритмов для вычисления расстояния Гильберта для 2 заданных точек (если это то, что здесь необходимо), которые используют битовые манипуляции и т. Д., Но не могли их понять вообще. Более того, я считаю, что цель задачи - самостоятельно выяснить, как рассчитать расстояние, а не использовать существующую формулу.

Есть кто-то, кто решил эту задачу и может помочь мне в дальнейшем? Спасибо!

Answer 1

Вот решение, которое я придумал:

1. Каждое местоположение точек может быть определено массивом квадрантов и их ориентацией (в ней будет N элементов) - каждый элемент представляет квадрант в предыдущем квадранте. Весь лабиринт, имеющий направленность вверх
2. Вам нужно определить этот массив для обеих точек. Например: если N = 2 и точка находится в нижнем левом квадранте, она будет иметь ориентацию влево. Мы берем этот квадрант и вращаем нашу систему координат, чтобы она имела ту же ориентацию. Таким образом, мы определяем следующую пару квадранта и ориентации в нашей новой системе. Таким образом, если у нас есть точка в левом нижнем квадранте, то она будет иметь ориентацию влево, но, поскольку это было относительно нашей предыдущей ориентации (которая была также слева), она станет ориентацией вверх.

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

   • если наша точка в нашем текущем квадранте находится на какой-либо из крайностей (имеется в виду, что любая из составляющих координаты является либо самой низкой, либо самой высокой из квадранта), мы оставляем ее там, где она была, в противном случае проверяем следующие точки
   • если наша точка находится внизу или в середине текущего квадранта, тогда мы переместимся в самую низкую среднюю точку квадранта (она идет относительно ранее определенной ориентации, то есть: если наша ориентация направлена ​​вверх, то мы переместим нашу точку в самую верхнюю среднюю точку)
   • если наша точка направлена ​​вверх (в относительном направлении), нам придется переместить ее в самую верхнюю среднюю точку

4. Сохраняя эти ходы, мы проверяем, есть ли у нас общие элементы в двух массивах, принадлежащих двум точкам:

   • в противном случае мы вычисляем расстояние между двумя конечными точками и суммируем все расстояния из списка двух перемещений (в этом списке каждое расстояние может быть рассчитано как вычитание компонента координат, то есть: abs(x1-x2) + abs(y1- у2))
   • если у нас есть общие элементы, то мы удаляем каждое движение после этого, включая общие элементы, и вычисляем расстояние, как указано в точке до

Это решение можно оптимизировать, оно просто предназначено для презентации и идеи для начала.

Изменить: Вот моя реализация представленного выше решения в Swift3: https://codility.com/demo/results/training9WWFXU-EWC/