Комментарии 4
заметим, что при таких величинах (1 за шаг "прямо" и 1000 за поворот) мы можем свести задачу к "за какое минимальное количество поворотов" можно достигнуть конечной точки.
Контрпример к данному поинту можно легко нарисовать на карте размером 6х520, а в условии, кажется, не было каких-то конкретных ограничений:
Карта
######
##.#.#
##.#.#
##.#.#
------ ещё куча строк "##.#.#"
##.#.#
##.#.#
#.E#S#
#.##.#
#....#
######В целом первая задача выглядит как на поиск кратчайших путей в графе и может быть решена Дейкстрой или UCS. В графе будет по 4 вершины на каждую клетку лабиринта, по количеству направлений (значения N, S, W, E - куда смотрит олень, вставший на клетку), причем, например, ребро между вершинами (i, j, N) и (i, j, W) имеет длину 1000 (это поворот на 90 гр), между вершинами (i, j, N) и (i, j, S) ребра нет, ибо бессмысленно, а ребро между (i, j, N) и (i, j-1, N) будет длиной 1. Мы стартуем из (i[S], j[S], E), смотрим кратчайшие пути до 4 вершин, относящихся к конечному квадратику. Всего ребер будет O(n), где n-количество клеток, и должно отработать за O(n * ln(n))
Контрпример к данному поинту можно легко нарисовать на карте размером 6х520
Очевидно, что можно, и это определенное допущение - только в реальном кейсе AoC дана карта 141x141, для которой мы такое можем себе позволить.
должно отработать за O(n * ln(n))
Тут проблема возникает ровно в хранении на каждом шаге минимального достигающего каждой клетки пути. То есть способов решения у этой задачи множество, но самый первый и наивный приведенный в статье - уже не отрабатывает за разумное время.
в реальном кейсе AoC дана карта 141x141
Это они зря. Недоработочка!
Ещё удивляет время выполнения первого запроса - 33 сек. Я просто скопировал его сюда и всё отлетело менее чем за секунду. Вы как запускали?
33 секунды - это для той самой "реальной" карты со стороной 141 - в контексте у плана есть полный запрос.
SQL HowTo: укрощаем рекурсию в лабиринте (Advent of Code 2024, Day 16: Reindeer Maze)