Los juegos de tácticas por turnos como Advance Wars, Wargroove y Fire Emblem están formados por una cuadrícula cuadrada de terreno variable con unidades de diferentes clases de movimiento que requieren diferentes costos para cada tipo de terreno. Investigaremos un subconjunto de ese problema.

Desafío

Su tarea es determinar si una ubicación es accesible desde otra dada una cuadrícula de costos del terreno y una velocidad de movimiento.

Las unidades solo pueden moverse ortogonalmente donde el costo de moverse a un cuadrado es el valor de la celda correspondiente en la cuadrícula (el movimiento es libre). Por ejemplo, pasar de una celda con un valor de 3 a una celda con un valor de 1 cuesta 1 movimiento, pero ir a la inversa requiere 3. Algunas casillas pueden ser inaccesibles.

Ejemplo

1 [1] 1  1  1
1  2  2  3  1
2  3  3  3  4
1  3 <1> 3  4

Moverse de [1]a <1>requiere un mínimo de 7 puntos de movimiento moviéndose hacia la derecha un cuadrado y luego hacia abajo tres. Por lo tanto, si se le da 6 o menos como la velocidad de movimiento, debe generar una respuesta falsa.

Ejemplos de casos de prueba

Estos utilizarán coordenadas de índice cero (fila, columna) de origen superior izquierdo en lugar de celdas entre corchetes para el inicio y el final para facilitar el análisis. Las celdas inalcanzables se representarán conX

Caso 1a

1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 5
From (2, 3) to (0, 1)

Output: True

Caso 1b

1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 4
From (2, 3) to (0, 1)

Output: False

Caso 1c

1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 5
From (0, 1) to (2, 3)

Output: False

Caso 2a

3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 7
From (3, 4) to (2, 1)

Output: True

Caso 2b

3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 4
From (3, 4) to (2, 1)

Output: False

Caso 2c

3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 7
From (1, 8) to (2, 7)

Output: True

Caso 3a

2 1 1 2
2 3 3 1
Speed: 3
From (0, 0) to (1, 1)

Output: False

Caso 3b

2 1 1 2
2 3 3 1
Speed: 3
From (1, 1) to (0, 0)

Output: True

Reglas, supuestos y notas

• Las lagunas estándar están prohibidas, las E / S pueden estar en cualquier formato conveniente
• Puede suponer que las coordenadas están todas en la cuadrícula
• La velocidad de movimiento nunca será superior a 100
• Las celdas inaccesibles pueden representarse con números muy grandes (por ejemplo, 420, 9001, 1 millón) o con 0 o nulo, lo que sea más conveniente para usted.
• Todas las entradas consistirán en enteros positivos (a menos que se use nulo o 0 para representar celdas inalcanzables)

Consulta TSQL, 205 191 bytes

La entrada es una variable de tabla @t

@ x = inicio xpos, @ y = inicio ypos @ i = fin xpos, @ j = fin ypos @ = velocidad

DECLARE @t table(x int,y int,v int)
INSERT @t
values
(0,0,1),(0,1,1),(0,2,2),(0,3,1),(0,4,null),
(1,0,1),(1,1,2),(1,2,2),(1,3,1),(1,4,1),
(2,0,2),(2,1,1),(2,2,1),(2,3,2),(2,4,1),
(3,0,null),(2,1,null),(2,2,null),(2,3,1),(2,4,2)

DECLARE @x INT=2,@y INT=3,@i INT=0,@j INT=1,@ INT=5;

WITH C as(SELECT @y f,@x r,@ s
UNION ALL
SELECT f+a,r+b,s-v FROM C
JOIN(values(1,0),(0,1),(-1,0),(0,-1))x(a,b)ON
s>0JOIN @t
ON f+a=x and r+b=y)SELECT
max(iif(S>=0and f=@j and r=@i,1,0))FROM c

Pruébelo en línea versión sin golf

Python 2 , 220 bytes

def f(m,a,w,h,r,c,R,C):
 T=[w*[999]for _ in' '*h];T[r][c]=0;P=[(r,c)];j,k=1,0
 for u,v in P:exec"U,V=u+j,v+k;j,k=-k,j\nif h>U>-1<V<w:q=T[U][V];T[U][V]=min(T[u][v]+m[U][V],q);P+=[(U,V)]*(q>T[U][V])\n"*4
 return a>=T[R][C]

Pruébalo en línea!

Toma una matriz mde enteros, con 'X'un valor mayor que 100; una velocidad a, que mtiene ancho wy alto h; y regresa donde podamos comenzar en la celda de fila / columna indexada a cero (r,c)y llegar a la celda final (R,C).

El algoritmo es un relleno de inundación modificado. Código levemente no golfista:

def f(m,a,w,h,r,c,R,C):
 T = [w*[999]for _ in ' '*h] # make an array same size as m, with all 
                             #   values 999, whose values will represent
                             #   the cost of getting to each cell.
 T[r][c] = 0                 # set the starting location to a cost of 0
 P = [(r,c)]                 # initialize a set of cells whose neighbors'
                             #   cost might need to be be updated
 j,k = 1,0                   # and also j,k which will take on values:
                             #  (1,0), (0,1), (-1,0), (0,1), used to 
                             #  probe orthogonal neighbors
 for u,v in P:               # scan the cells in P
    for _ in '1234':         # look at each of 4 orthogonal positions
        U,V = u+j,v+k        # U and V get the indexes of a neighbor 
                             #   of the current cell.
        j,k = -k,j           # this 'rotates' the j,k pairing.
        if h>U>-1<V<w:       # if the coordinates are in bounds...
            q = T[U][V]      # save the current 'cost' of getting to cell (U,V)
                             # see if we can reduce that cost, which is calculated 
                             #   by taking the cost of the currently scanned cell 
                             #   + the value from m for the neighbor cell. 
            T[U][V] = min(T[u][v]+m[U][V] ,q)
                             # if we can reduce the cost, add the neighbor
                             #   to P because **it's** neighbors might,
                             #   in turn, need updating.
            P += [(U,V)]*(q>T[U][V])
 return a>=T[R][C]           # return if speed is enough for the cost.

JavaScript (ES7),  116  113 bytes

(matrix)([endRow, endCol])(speed, startRow, startCol)$0$$1$

m=>e=>o=g=(s,y,x)=>m.map((r,Y)=>r.map((v,X)=>r[s<v|(x-X)**2+(y-Y)**2-1||g(s-v,Y,X,r[X]=1/0),X]=v),o|=y+[,x]==e)|o

Pruébalo en línea!

Comentado

m =>                        // m[] = matrix
e =>                        // e[] = target coordinates
  o =                       // o   = success flag, initialized to a non-numeric value
  g = (                     // g   = recursive depth-first search function taking:
    s,                      //   s    = speed
    y, x                    //   y, x = starting coordinates
  ) =>                      //
    m.map((r, Y) =>         // for each row r[] at position Y in m[]:
      r.map((v, X) =>       //   for each value v at position X in r[]:
        r[                  //     this statement ultimately updates r[X]:
          s < v |           //       abort if s is less than v
          (x - X) ** 2 +    //       or the quadrance between (x, y)
          (y - Y) ** 2 - 1  //       and (X, Y) is not equal to 1
          || g(             //       otherwise, do a recursive call to g:
               s - v,       //         subtract v from s
               Y, X,        //         pass (Y, X) as the new coordinates
               r[X] = 1 / 0 //         temporarily make this cell unreachable
             ),             //       end of recursive call 
          X                 //       restore r[X] ...
        ] = v               //     ... to its original value
      ),                    //   end of inner map()
      o |= y + [, x] == e   //   set the flag o if (y + ',' + x) matches (e + '')
    ) | o                   // end of outer map(); return o

Jalea , 59 bytes

+2¦µ_2ịæ.ؽœị$Ʋ+5ịƲ$4¦01Ñḣ3Ḋ⁼/Ɗ?ḣ2=/ẸƊoF<0ẸƊƊ?
çⱮØ.,U$;N$¤Ẹ

Pruébalo en línea!

No es terriblemente rápido; intenta todos los caminos hasta que las unidades de velocidad se agoten, incluso volviendo sobre sus pasos Sin embargo, esto evita la necesidad de verificar si se visitan espacios. La entrada se proporciona como[nrows, ncols],[start_row, start_col],[end_row, end_col],speed,flattened matrix column-major

Explicación

Enlace auxiliar

+2¦                                       | add the right argument to the second item in the left argument (current location)
   µ                                      | start a new monadic chain with the modified left argument
                    4¦                    | for the fourth item (speed)...
    _                                     |   subtract...
                 ịƲ$                      |     the item located at...
     2ịæ.ؽœị$Ʋ                           |       the dot product of the current position and (number of columns,
                                          |       right-padded with 1)
               +5                         |       plus five
                                        ? | Now, if...
                                       Ɗ  |   next three as a monad
                           ḣ2=/ẸƊ         |   either current row or current column are equal to nrows/ncolumns respectively
                                 o        | or
                                  F<0ẸƊ   |   any value is negative
                 0                        | return zero
                          ?               | else if...
                   ḣ3Ḋ⁼/Ɗ                 | the second and third items (current and end pos) are equal
                  1                       | return 1
                   Ñ                      | else pass the current list back to the main link

Enlace principal

ç             | call the helper link with the current list...
 Ɱ            |   and each of
  Ø.,U$;N$¤   |   [0,1],[1,0],[0,-1],[-1,0]
           Ẹ  | Check if any are true

Jalea , 38 bytes

ạƝṢ€Ḅ’¬Ạ
ŒṪ’ḟŒPŒ!€ẎW€j¥@€ÇƇḊ€‘œị⁸§Ṃ’<⁵

Un programa completo extremadamente ineficiente que acepta el terreno (con invisibles como 101), luego las coordenadas de inicio y fin, luego la velocidad.

Pruébalo en línea! (¡no tiene mucho sentido probar la mayoría de los casos de prueba!)

¿Cómo?

Crea una lista de todas las permutaciones de cada uno de los conjuntos de potencia de "todas las ubicaciones del terreno, excepto el inicio y el final", rodea cada uno de estos con el inicio y el final, filtra a aquellos que solo realizan movimientos ortogonales de distancia uno, suelta el inicio de cada uno, indexa nuevamente en el terreno, suma cada uno, toma el mínimo, resta uno y prueba que esto es menor que la velocidad.