Вы водитель такси в Сан-Франциско. Как это характерно для водителей такси, вы перемещаетесь по сетке, где единственными действительными направлениями, которые вы можете перемещать, являются левый, правый, вверх и вниз. Однако Сан-Франциско очень холмистый, поэтому расстояние между двумя соседними перекрестками не обязательно одинаково. Более конкретно, расстояние между пересечением на высоте a
и соседним пересечением на высоте b
будет 1 + |a - b|
. Ваша цель - найти все кратчайшие пути от вашего источника в верхнем левом углу карты до пункта назначения в нижнем правом углу.
вход
Двумерная сетка целочисленных высот в любом удобном формате (двумерный массив, одномерный массив с шириной и / или высотой и т. Д.).
Выход
Последовательность направлений для перемещения в нижний правый угол ввода сверху слева на кратчайшем возможном расстоянии с учетом расстояния между двумя смежными пересечениями высот a
и b
задается формулой 1 + |a - b|
. Если существует несколько решений, выведите все решения.
Хотя я использую U
, D
, L
и R
для вверх, вниз, влево и вправо в примерах ниже вашей программы могут использовать любые четыре различных строки для представления направления так долго , как это согласуется с ними и на всех входах.
Примеры
Input:
0 3 0 0 0
0 2 0 2 0
0 0 0 3 0
Output:
D D R R U U R R D D
Input:
3
Output:
<empty>
Input:
11 11 11
11 11 11
11 11 11
Output:
R R D D
R D R D
R D D R
D R R D
D R D R
D D R R
Input:
7 8 1 -1 0
4 4 6 -1 7
3 4 4 2 8
2 5 2 -1 2
Output:
D R D R R D R
D R D R D R R
Это код-гольф, поэтому выигрывает ответ с самым коротким числом байтов.
Ответы:
JavaScript (ES6),
228212200194 байтавход
Одномерный массив
a
и ширинаw
в синтаксисе каррирования(a)(w)
Выход
Разделенный пробелами список решений, таких как
"DRDRRDR DRDRDRR"
Отформатировано и прокомментировано
Контрольные примеры
Показать фрагмент кода
источник