La tortuga quiere moverse a lo largo de la cuadrícula para llegar a su comida. Quiere saber cuántos movimientos le tomará llegar allí.

Además, dado que es lento, tiene teletransportadores configurados alrededor de su dominio que utilizará si acorta su camino. O evítalos si alarga su camino.

Conoce a la tortuga

🐢

La tortuga vive en una cuadrícula La tortuga puede moverse a cualquier cuadrado adyacente ...

$$\begin{matrix} X&X&X&X&X\\ X&X&X&X&X\\ X&X&🐢&X&X\\ X&X&X&X&X\\ X&X&X&X&X\\ \end{matrix}$$ $$\begin{matrix} X&X&X&X&X\\ X&\nwarrow&\uparrow&\nearrow&X\\ X&\leftarrow&🐢&\rightarrow&X\\ X&\swarrow&\downarrow&\searrow&X\\ X&X&X&X&X\\ \end{matrix}$$

Sin embargo, la tortuga no puede moverse a un cuadrado con una montaña

$$\begin{matrix} X&🌄&X&X&X\\ X&\nwarrow&\uparrow&\nearrow&X\\ X&🌄&🐢&\rightarrow&X\\ X&🌄&\downarrow&\searrow&X\\ X&🌄&X&X&X\\ \end{matrix}$$

La tortuga quiere comer su fresa, y le gustaría saber cuánto tiempo le llevará llegar a su fresa Este ejemplo llevaría a la tortuga vueltas Por suerte, ¡La tortuga encontró un teletransportador! Hay dos teletransportes en la cuadrícula que se asignan entre sí. Al pisar el teletransportador, la tortuga se mueve inmediatamente al teletransportador correspondiente. Los teletransportadores son muy inestables y después de usarlos una vez, desaparecen y ya no se pueden usar.

$$\begin{matrix} X&🌄&🍓\\ 🐢&🌄&X\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$ $5$ $$\begin{matrix} X&🌄&🍓\\ \downarrow&🌄&\uparrow\\ \searrow&🌄&\uparrow\\ X&\nearrow&X\\ \end{matrix}$$ $$\begin{matrix} 🔵&🌄&🍓\\ 🐢&🌄&🔴\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$ Ahora es más rápido para la tortuga subir dos veces. Ahora el camino más corto de las tortugas es $2$ $$\begin{matrix} 🔵&🌄&🐢\\ \uparrow&🌄&🔴\uparrow\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$

El reto

Dada una salida de configuración de cuadrícula inicial, el número de movimientos que le tomará a la tortuga alcanzar su fresa.

Reglas

• Puede suponer que la cuadrícula de entrada tiene una solución

• Cada cuadrícula solo tendrá uno strawberryy dos portalsy unoturtle

• La cuadrícula de entrada se puede ingresar en cualquier formato conveniente

• Debes tratar los teleportersartículos de un solo uso.

• El turno en que la tortuga se mueve hacia un teleportercuadrado ya está en el correspondiente teleporter. Nunca se mueve hacia a teleportery se queda allí para moverse.

• El camino más corto no necesita hacer uso del portal

• La tortuga no puede pasar a los azulejos de la montaña.

• Se puede usar cualquier carácter ASCII o entero para representar mountains, turtle, empty grid square,strawberry

• Puede usar el mismo carácter o dos caracteres ASCII o enteros diferentes para representar los teleporterpares

• Una cuadrícula puede tener más de una ruta con la misma longitud de ruta más corta

• Esto es código golf

Aclaraciones a las reglas

• Debe tratar teleportersson artículos de un solo uso.

Razonamiento : Se señaló que el caso de:

$$\begin{matrix} 🐢&X&🔵&X&🍓\\ 🌄&🌄&🌄&🌄&🌄&\\ 🔴&X&X&X&X \end{matrix}$$

Solo podría resolverse entrando y saliendo de los portales dos veces. En el momento de hacer esta aclaración, ambas soluciones actuaron asumiendo que eran de un solo uso, o que no había razón para probar cuadrados usados ​​previamente. Para evitar romper sus soluciones tan trabajadas, esta parecía la mejor forma de explicar esta configuración. Por lo tanto, esto se consideraría una cuadrícula no válida.

Casos de prueba formateados como listas

[ ['T', 'X', 'X', 'S', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 3
[ ['T', 'M', 'X', 'S', 'X'], ['X', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'O'] ] --> 4
[ ['T', 'M', 'X', 'S', 'O'], ['O', 'M', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 2
[ ['T', 'M', 'X', 'S', 'X'], ['O', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'X'] ] --> 4
[ ['T', 'M', 'S', 'X', 'O'], ['X', 'M', 'M', 'M', 'M'], ['X', 'X', 'X', 'X', 'O'] ] --> 7
[ ['T', 'X', 'X', 'S', 'X'], ['O', 'M', 'M', 'M', 'X'], ['X', 'X', 'O', 'X', 'X'] ] --> 3

Casos de prueba formateados para humanos

T X X S X
X X X X X
X X X X X --> 3

T M X S X
X M X X X
O X X X O --> 4

T M X S O
O M X X X
X X X X X --> 2

T M X S X
O M X X X
O X X X X --> 4

T M S X O
X M M M M
X X X X O --> 7

T X X S X
O M M M X
X X O X X --> 3

Créditos

Diseño y estructura a través de: Ratón hambriento de Arnauld

Desafíos propuestos Editar consejo: Kamil-drakari , beefster

Consejo de edición general: okx nedla2004 mbomb007

JavaScript (ES7),  140 139  138 bytes

Toma datos como una matriz de enteros con la siguiente asignación:

• $-1$
• $0$$X$
• $1$
• $2$
• $3$

m=>(R=g=(t,X,Y,i)=>m.map((r,y)=>r.map((v,x)=>r[(u=0,t?v-t:(x-X)**2+(y-Y)**2<3?v-3?~v?v:u--:R=R<i?R:i:1)||g(u,x,y,u-~i,r[x]=1),x]=v)))(2)|R

Pruébalo en línea!

¿Cómo?

$g$$t$$t\ne 0$$(x,y)$$(X,Y)$

$i$$R$$\min(R,i)$

$t=2$

$t=-1$$i$

$R$

Comentado

m => (                        // m[] = input matrix
  R =                         // initialize R to a non-numeric value
  g = (t, X, Y, i) =>         // g = recursive search function taking t = expected tile,
                              //     (X, Y) = current coordinates, i = path length
    m.map((r, y) =>           // for each row r[] at position y in m[]:
      r.map((v, x) =>         //   for each tile v at position x in r[]:
        r[                    //     this statement will eventually restore r[x] to v
          ( u = 0,            //     u = next tile to look for, or 0 if none
            t ?               //     if we're looking for a specific tile:
              v - t           //       test whether we've found it
            :                 //     else:
              (x - X) ** 2 +  //       compute the squared Euclidean distance between
              (y - Y) ** 2    //       (x, y) and (X, Y)
              < 3 ?           //       if it's less than 3 (i.e. reachable from (X, Y)):
                v - 3 ?       //         if v is not equal to 3:
                  ~v ?        //           if v is not equal to -1:
                    v         //             test if v = 0
                  :           //           else (v = -1):
                    u--       //             set u = -1 to find the other portal
                :             //         else (v = 3):
                  R = R < i ? //           we've found the strawberry: set R = min(R, i)
                      R : i   //
              :               //       else (this tile can't be reached):
                1             //         yield 1
          ) ||                //     if the above result is falsy:
          g(                  //       do a recursive call:
            u,                //         t = u
            x, y,             //         move to (x, y)
            u - ~i,           //         unless u is set to -1, increment i
            r[x] = 1          //         set this tile to a mountain
          ),                  //       end of recursive call
          x                   //     restore r[x] ...
        ] = v                 //     ... to v
    ))                        // end of both map() loops
)(2) | R                      // initial call to g with t = 2; return R

Python 2 , 441 431 341 bytes

from itertools import*
G=input()
W=len(G[0])
H=len(G)
A=[0]*5
E=enumerate
for y,r in E(G):
 for x,C in E(r):A[C]=[x,y]
for L in count():
 for M in product(*[zip('UDLR'*2,'LRDU    ')]*L):
  x,y=A[0]
  for m in M:
    x+='R'in m;x-='L'in m;y+='D'in m;y-='U'in m
    if(x,y)==A[3]:x,y=A[2]
    if 1-(W>x>-1<y<H)or G[y][x]>3:break
  if[x,y]==A[1]:exit(L)

Pruébalo en línea!

Ingrese como listas, pero utilizando números en lugar de caracteres (gracias a Quintec) y un valor separado para el destino del teletransportador. Esas sangrías grandes deben ser caracteres de tabulación si Stack Exchange las elimina. Cualquier consejo o idea especialmente bienvenida, ya que creo que esto podría ser mucho más corto.

La tabla para los caracteres utilizados en el desafío a los números utilizados para mi programa está a continuación, pero también puede utilizar este programa .

Challenge | My program
T         | 0
S         | 1
E         | 2
O         | 3
M         | 4
X         | -1

-10 bytes gracias a Quintec al cambiar la entrada del uso de caracteres a números.

-Muchos bytes gracias a Jonathan Frech, ElPedro y Jonathan Allan.

Python 2 , 391 397 403 422 bytes

M=input()
from networkx import*
a=b=c=d=0
N,h,w,S=[-1,0,1],len(M),len(M[0]),[]
for i in range(h):
 for j in range(w):
  I,m=(i,j),M[i][j]
  if m>7:c,d=a,b;a,b=I
  if m<0:Z=I
  if m==5:F=I
  S+=[I+I]
S+=[(a,b,c,d),(c,d,a,b)]
print len(shortest_path(from_edgelist([((A+p,B+q),(C,D))for A,B,C,D in S for p,q in[(p,q)for p in N for q in N]if-1<A+p<h and-1<B+q<w and M[C][D]*M[A+p][B+q]]),Z,F))-1

Pruébalo en línea!

El problema se traduce en un gráfico y la solución es encontrar el camino más corto desde la tortuga hasta la fresa.

Challenge | This code
T         | -1
S         |  5
O         |  8
M         |  0
X         |  1