Я стою в точке (0,0)
на карте H
x, W
где высота представлена цифрами, например:
1132
2221
1230 # H = 3, W = 4
Я хотел бы испытать взгляды от каждой вершины, которые в данном случае являются областями с высотой 3
. Однако взбираться на холмы - непростая задача, и у меня тоже не хватает времени.
Вызов
Задача состоит в том, чтобы найти самый быстрый путь, чтобы посетить все вершины и вернуться.
Кратчайшая программа выигрывает.
вход
- H, W - высота и ширина карты (целые числа) (необязательно, может быть списком / кортежем или двумя отдельными целочисленными входами)
- Карта, представленная в виде
H
набораW
цифр (0
-9
), в любом удобном формате (2D-список, строка, разделенная символом новой строки и т. Д.)
Выход
- Наименьшее время, необходимое для посещения каждой вершины и возврата к исходной точке (целое число)
условия
- Высота данной области представлена цифрой от
0
до9
. - «Пик» определяется районом с наибольшей высотой.
- Путь должен начинаться и заканчиваться в верхней левой (0,0) области.
- Вы можете перемещаться только в области, прилегающие к вашей текущей области, и вы не можете двигаться по диагонали.
- Перемещение из одного района в другой занимает 3 минуты, если высота не меняется.
- Требуется 11 минут, чтобы подняться; то есть, перемещаясь из одной области в другую область, которая точно на
1
единицу выше. - Это займет 2 минуты, чтобы спуститься вниз; то есть, перемещаясь из одной области в другую область, которая точно на
1
единицу ниже. - Вы не можете перемещаться в области, которые больше чем на
1
единицу выше или ниже, чем там, где вы находитесь. (Вы не можете перейти из области с высотой1
в соседнюю область с высотой, скажем,3
)
- Путь ко всем вершинам гарантирован
- Максимальное количество пиков есть
15
.
образцы
вход
4 5
32445
33434
21153
12343
Выход
96
объяснение
Вы начинаете сверху слева 3
. Вы должны посетить две точки 5
, которые расположены в (0,4)
и (3,3)
и вернуться 3
в (0,0)
в кратчайшие сроки.
3 2 4->4->5
V ^
3->3->4 3 4
2 1 1 5 3
1 2 3 4 3 # 3 + 3 + 11 + 3 + 3 + 11 = 34 minutes to visit 1st peak
3 2 4 4 5
V
3 3 4 3 4
V
2 1 1 5 3
^ V
1 2 3 4<-3 # 2 + 2 + 3 + 11 + 11 = 29 minutes to visit 2nd
3 2 4 4 5
^
3 3 4 3 4
^
2 1 1 5 3
^ V
1<-2<-3<-4 3 # 2 + 2 + 2 + 2 + 11 + 11 + 3 = 33 minutes to come back
# 34 + 29 + 33 = 96 minutes total is the answer
вход
2 7
6787778
5777679
Выход
75
code-golf
path-finding
puzzle-solver
graph-theory
cozyconemotel
источник
источник
Ответы:
Mathematica
745681 байтОсновная идея - составить взвешенный график возможных ходов. Вес - это время, необходимое для перемещения из одного места в другое. Путь с наименьшим весом будет самым быстрым.
Входные цифры помещаются в прямоугольный массив r by c (строки по столбцам), а затем в игру вступают три различных представления: (1) граф сетки r by c, где каждая вершина соответствует ячейке в массиве, (2) (r c) посредством (r c) взвешенной матрицы смежности, которая содержит весовые коэффициенты, соответствующие времени, которое требуется (2, 3 или 11 минут) для перемещения из одного местоположения (в графе сетки) в другое, и (3) направленного взвешенный граф смежности, построенный из матрицы.
Граф сетки помогает определить, какие ячейки (то есть, какие вершины) возможно достижимы из каждой вершины - «возможно достижимы», потому что соседняя ячейка должна быть не только справа, слева, выше или ниже данной ячейки. Его значение также должно быть в пределах 1 единицы расстояния от соседа (например, 3 не соединяется с соседним 5 или 1). Если вершина
a
не связана с вершиной,b
то ячейки матрицы смежности {a, b} и {b, a} будут иметь значение ∞. Соответственно, взвешенный граф смежности не будет иметь ребра ни от a до b, ни от b до a.Взвешенный граф смежности служит для определения минимального расстояния (
GraphDistance
) и кратчайшего маршрута между любыми вершинами. Оптимальный путь должен начинаться с 1, касаться каждого из пиков и возвращаться к 1. В этом случае «кратчайший маршрут» не обязательно тот, который имеет наименьшее количество ходов. Это время с наименьшим общим временем, измеренным в весах ребер.Golfed
Более длинная, более читаемая форма
тесты
96.
75.
51.
объяснение
Подумайте о строках 2-5 следующего ввода
как представляющий массив с 4 строками и 5 столбцами:
где каждая вершина соответствует цифре из входного массива: 3 - в вершине 1, 2 - в вершине 2, 4 - в вершине 3, еще 4 - в вершине 4, 5 - в вершине 5 и т. д. Граф сетки является лишь грубым аппроксимация графика, к которому мы стремимся. Это не направлено. Кроме того, некоторые края будут недоступны. (Помните: мы не можем перейти из положения в другое, которое больше, чем на 1 единицу высоты выше или ниже текущей.) Но график сетки позволяет нам легко находить те вершины, которые находятся рядом с любой выбранной вершиной. Это уменьшает количество ребер, которые мы должны рассмотреть, в первом примере (сетка 4 на 5) с 400 (20 * 20) до 62 (31 * 2 - количество ребер в графе сетки). В том же примере только 48 ребер являются действующими; 14 нет.
Следующая взвешенная матрица смежности 20 на 20 представляет расстояние между всеми парами вершин от графа сетки.
Код ключа, который решает, какой номер назначить, указан ниже.
Ячейка {1,2} - в одноиндексации - содержит значение 2, потому что движение от вершины 1 к вершине 2 идет вниз. Ячейка {2,1} содержит 11, потому что движение от вершины 2 к вершине 1 идет в гору. 3 в ячейках {1,6} и {6,1} означают, что движение не идет ни вверх, ни вниз. Ячейка {1,1} содержит ∞, потому что она не связана с собой.
На следующем графике показана структура, лежащая в основе вышеуказанного ввода. Цветные стрелки показывают оптимальный путь от вершины 1 до пиков (в 5 и 14) и обратно до 1. Синие стрелки соответствуют движениям на том же уровне (3 мин); красные стрелки обозначают подъем (11 мин.), а зеленые стрелки обозначают снижение (2 мин).
Путь от вершины 1 (ячейка {1,1} к двум вершинам и обратно к вершине 1:
96
источник
Pyth, 92 байта
Входной формат является ДИКТ отображения координат на высоты:
{(0, 0): 3, (0, 1): 2, (0, 2): 4, …}
. Это находит самые быстрые пути между всеми парами точек, используя алгоритм Флойда-Варшалла , а затем минимизирует общее время требуемого цикла по всем перестановкам пиков.Попробуйте онлайн
источник