Usted es un taxista en San Francisco. Como es típico de los conductores de taxis, está navegando por una cuadrícula donde las únicas direcciones válidas que puede mover son la izquierda, derecha, arriba y abajo. Sin embargo, San Francisco es muy montañoso, por lo que la distancia entre dos intersecciones adyacentes no es necesariamente la misma. Más específicamente, la distancia entre una intersección en altitud a
y una intersección adyacente en altitud b
sería 1 + |a - b|
. Su objetivo es encontrar todos los caminos más cortos desde su origen en la parte superior izquierda del mapa hasta su destino en la parte inferior derecha.
Entrada
Una cuadrícula bidimensional de altitudes enteras en el formato más conveniente (matriz bidimensional, matriz unidimensional con ancho y / o alto, etc.).
Salida
Una secuencia de direcciones para viajar para llegar a la esquina inferior derecha de la entrada desde la parte superior izquierda en la distancia más corta posible dada la distancia entre dos intersecciones adyacentes de altitudes a
y b
está dada por la fórmula 1 + |a - b|
. Si hay varias soluciones, envíe todas las soluciones.
Aunque yo uso U
, D
, L
, y R
para arriba, abajo, izquierda y derecha en los ejemplos que siguen su programa puede utilizar cualquiera de los cuatro series diferentes para representar las direcciones, siempre que sea compatible con ellos en ya través de todas las entradas.
Ejemplos
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
Este es el código de golf, por lo que la respuesta con el conteo de bytes más corto gana.
Respuestas:
JavaScript (ES6),
228212200194 bytesEntrada
Matriz unidimensional
a
y anchow
en sintaxis de curry(a)(w)
Salida
Una lista de soluciones separadas por espacios, como
"DRDRRDR DRDRDRR"
Formateado y comentado
Casos de prueba
Mostrar fragmento de código
fuente