Dada una cuadrícula de direcciones y una posición inicial y final, determine el número mínimo de sustituciones en la cuadrícula de dirección que debe realizarse para completar el camino entre los dos puntos. La cuadrícula es doblemente cilíndrica. Esto está más claro dado un ejemplo.

Ejemplo

Tomemos la siguiente cuadrícula como ejemplo:

>>>>v
>>>><
<<<<<

Comencemos por (1, 1)y terminemos en (1, 3)(donde están las coordenadas (x, y)o (col, row), con la fila superior y la columna izquierda 1). Entonces, una posible solución es reemplazar el (1, 1)y (1, 2)con v, para que la grilla final se vea así:

v>>>v
v>>><
<<<<<

A partir de (1, 1), el camino nos llevaría a (1, 3). Sin embargo, existe una solución más corta, que es reemplazar (5, 2)con v, por lo que la grilla final es esta:

>>>>v
>>>>v
<<<<<

A partir de (1, 1), un camino bastante largo conduce a (1, 3).

Reemplazar cualquier cosa en la fila superior con ^trabajos también (gracias @Spitemaster).

Entrada

La entrada consistirá en una cuadrícula rectangular de 4 valores posibles, así como dos coordenadas. Puede tomar la cuadrícula en cualquier formato razonable; por ejemplo, matriz de caracteres o enteros, lista de cadenas, etc. También puede solicitar las dimensiones de la cuadrícula. Puede tomar las coordenadas en cualquier formato razonable; por ejemplo, par entero, número complejo, etc. Puede elegir indexación 0 o 1.

Salida

La salida debe ser un número entero, el número mínimo de reemplazos de cuadrícula necesarios para cerrar la ruta desde el principio hasta el final.

Reglas y especificaciones

• Se aplican lagunas estándar
• la cuadrícula es doblemente cilíndrica, lo que significa que moverse hacia arriba desde la parte superior va hacia abajo, la izquierda desde la izquierda hacia la derecha, etc.

Casos de muestra

Los casos de muestra se proporcionan como una matriz de caracteres y coordenadas indexadas 1.

Caso 1

Entrada

>>>>v
>>>><
<<<<<
1 1
1 3

Salida

1

Explicación

Ver ejemplo.

Caso 2

Entrada

<<<<<
v>v>v
>>>>>
1 1
5 3

Salida

1

Explicación

Puede reemplazar (1, 1)con vo (2, 1)con v. En el primer caso, comenzando desde (1, 1), el camino va directo hacia abajo y luego a la derecha hacia el destino. En el segundo caso, el camino gira de la izquierda a la derecha, llega (2, 1), baja, derecha, abajo y luego a la derecha hasta llegar al destino.

Caso 3

Entrada

^^^^^^
><<>>>
vvvvvv
2 2
5 2

Salida

2

Explicación

El mejor cambio es hacer que la fila central se ajuste alrededor de la izquierda al punto; es decir, haga el primer y el último elemento en la fila central <. Alternativamente, hacer 2 2y 3 2ambos >.

Este es un desafío de código de golf , por lo que gana el código más corto

JavaScript (ES6),  140  135 bytes

Toma datos como (a, width, height, x1, y1)(x0, y0)donde a[]está una matriz de enteros y todas las coordenadas están indexadas a 0.

$-2$$-1$$0$$1$

(a,w,h,X,Y)=>m=g=(x,y,n=0,r=a[y%=h],v=r[x%=w])=>x-X|y-Y?[-1,0,1,2].map(d=>r[v<2&&g(x+w+d%(r[x]=2),y+h+--d%2,n+(v!=d)),x]=v)|m:m=m<n?m:n

Pruébalo en línea!

¿Cómo?

$(x,y)$$(X,Y)$

$n$

$m$$n$

Gelatina , 73 72 bytes

W,0+Ɱ⁴PṬ€×Ɱ3¤Ẏ¤,€ɗ/€Ẏ$‘ƭ€ịØ.,N;U$¤;ɗ/0ị+æ.Ɱ⁴‘Ṫịʋ¥Ɗ%⁴ṭƲ⁴P¤¡ŒHṪe¥/Ʋ€Ẹ¬Ɗ/¿Ṫ

Pruébalo en línea!

Ejemplo usando el caso 3 que requiere dos cambios (también tiene un pie de página para traducirlos ><v^a números).

Un programa completo que espera los siguientes argumentos:

• Izquierda: una lista de dos listas; primero la cuadrícula de dirección aplanada codificada como 1 = derecha, 2 = izquierda, 3 = abajo, 4 = arriba, seguido de una lista de la posición final y la posición inicial como índices cero [fila, columna]. Para el primer ejemplo [1,1,1,1,3,1,1,1,1,4,2,2,2,2,2],[[2,0],[0,0]],.

• Derecha: una lista de la cantidad de filas seguidas de columnas. Para el primer ejemplo[3,5]

Devuelve el número de cambios necesarios para obtener de principio a fin. Reduzca la velocidad una vez que esto sea más de un cambio. En TIO, el tercer caso de ejemplo toma aprox. 30 segundos para completar.

La explicación completa a continuación, pero la descripción general es:

1. Inicializa un contador a cero.
2. $\mathit{row} × \mathit{column}$
3. Compruebe si la posición final está incluida:
   • $3 × \mathit{row} × \mathit{column}$
   • Si es verdadero, termina y genera el contador

Explicación completa:

W,0 | Wrap input in a list, and then pair with 0 (thus initialising the counter)


                                           Ɗ/¿ | While the following is true for the first item of the input pair (i.e. the list of all grids to be tested, paired with the end and start grid positions):
                                       Ʋ€      | - For each member of the list:
          ɗ/                                   |   - Reduce using the following as a dyad (so left argument is flattened grid and right is end/start positions)
ị       ¤                                      |     - Index into the following as a nilad
 Ø.                                            |       - [0, 1]
   ,N                                          |       - Pair with negative [[0, 1], [0, -1]]
     ;U$                                       |       - Concatenate to upended version of this [[0, 1], [0, -1], [1, 0], [-1, 0]]
         ;                                     |     - Concatenate (to end/start positions)
                            Ʋ⁴P¤¡              |   - Repeat the following links the number of times indicated by the product of the grid dimensions:
                        Ɗ                      |     - Following as a monad:
            0ị                                 |       - Last item (current grid position)
              +        ¥                       |       - Add to the following as a dyad:
               æ.Ɱ⁴                            |         - Dot product of current position with each of grid dimensions
                   ‘                           |         - Increase by 1
                    Ṫ                          |         - Tail (which is current position in flattened grid)
                     ị                         |         - index into flattened grid
                         %⁴                    |        - Mod grid dimensions
                           ṭ                   |        - Tack onto end of current grid/position list
                                 ŒH            |   - Split into halves (first half will be flattened grid and desired end position, second half will be all positions reached after moving through grid)
                                     ¥/        |   - Following as a dyad, with the first half from above step as left argument and the second half as right
                                   Ṫ           |     - Tail (i.e. the desired end position)
                                    e          |     - Exists within (the list of all positions reached)
                                         Ẹ¬    | - Not true for any of the input grids


                    ƭ€ | For each of the pair (list of grids, counter), do one of the following:
                  $    | - For the list of grids, do the following as a monad:
              ɗ/€      |   - Do the following as a dyad, with the flattened grid as the left argument and end/start positions as the right:
+Ɱ                     |     - Add to the flattened grid list each of:
           ¤           |       - The following as a nilad
         ¤             |         - The following as a nilad:
  ⁴P                   |           - The product of the grid dimensions
    Ṭ€                 |           - Convert each (using an implicit range from 1 to the grid dimension product) to a boolean list with a 1 at the relevant position (i.e. [[1], [0, 1], [0, 0, 1]...])
      ×Ɱ3              |           - Multiply by each of 1..3
          Ẏ            |        - Flatten to a single list of lists
            ,€         |    - Pair each with the end/start positions
                 Ẏ     |   - Tighten to a single list of grids paired with end/start positions
                   ‘   | - For the counter increment it


Ṫ | Finally, take the tail (which is the final value of the counter)