Les jeux tactiques au tour par tour comme Advance Wars, Wargroove et Fire Emblem sont constitués d'une grille carrée de terrain variable avec des unités de classes de mouvement différentes nécessitant des coûts différents pour chaque type de terrain. Nous allons enquêter sur un sous-ensemble de ce problème.

Défi

Votre tâche consiste à déterminer si un emplacement est accessible à partir d'un autre étant donné une grille de coûts de terrain et une vitesse de déplacement.

Les unités ne peuvent se déplacer orthogonalement que lorsque le coût de déplacement sur un carré est la valeur de la cellule correspondante sur la grille (le déplacement est gratuit). Par exemple, passer d'une cellule de valeur 3 à une cellule de valeur 1 coûte 1 mouvement, mais aller dans l'autre sens nécessite 3. Certains carrés peuvent être inaccessibles.

Exemple

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

Passer de [1]à <1>nécessite un minimum de 7 points de mouvement en se déplaçant vers la droite d'un carré puis vers le bas de trois. Ainsi, si donné 6 ou moins comme vitesse de déplacement, vous devriez produire une réponse fausse.

Exemples de cas de test

Ceux-ci utiliseront des coordonnées indexées en haut à gauche (ligne, colonne) plutôt que des cellules entre crochets pour le début et la fin afin de faciliter l'analyse. Les cellules inaccessibles seront représentées parX

Cas 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

Cas 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

Cas 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

Cas 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

Cas 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

Cas 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

Cas 3a

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

Output: False

Cas 3b

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

Output: True

Règles, hypothèses et notes

• Les failles standard sont interdites, les E / S peuvent être dans n'importe quel format pratique
• Vous pouvez supposer que les coordonnées sont toutes sur la grille
• La vitesse de déplacement ne dépassera jamais 100
• Les cellules inaccessibles peuvent être représentées avec de très grands nombres (par exemple 420, 9001, 1 million) ou avec 0 ou nul, selon ce qui vous convient le mieux.
• Toutes les entrées seront constituées d'entiers positifs (sauf si vous utilisez null ou 0 pour représenter des cellules inaccessibles)

Requête TSQL, 205 191 octets

L'entrée est une variable de table @t

@ x = début xpos, @ y = début ypos @ i = fin xpos, @ j = fin ypos @ = vitesse

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

Essayez-le en ligne version non golfée

Python 2 , 220 octets

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]

Essayez-le en ligne!

Prend un tableau md'entiers, avec 'X'comme valeur supérieure à 100 ;, une vitesse a, mayant une largeur wet une hauteur h; et retourne où nous pouvons commencer à la cellule de ligne / colonne indexée zéro (r,c)et arriver à la cellule finale (R,C).

L'algorithme est un remplissage inondé modifié. Code légèrement non golfé:

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),  116113  octets

(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

Essayez-le en ligne!

Commenté

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

Gelée , 59 octets

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

Essayez-le en ligne!

Pas terriblement rapide; tente tous les chemins jusqu'à ce que les unités de vitesse soient épuisées, retraçant même ses pas. Cependant, cela évite d'avoir à vérifier si les espaces sont visités. L'entrée est fournie comme[nrows, ncols],[start_row, start_col],[end_row, end_col],speed,flattened matrix column-major

Explication

Lien d'aide

+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

Lien 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

Gelée , 38 octets

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

Un programme complet extrêmement inefficace acceptant le terrain (avec des invisibles comme 101) puis les coordonnées de début et de fin puis la vitesse.

Essayez-le en ligne! (pas grand chose à essayer la plupart des cas de test!)

Comment?

Crée une liste de toutes les permutations de chacun des ensembles de puissance de "tous les emplacements de terrain sauf le début et la fin", entoure chacun d'eux avec le début et la fin, filtre ceux qui ne font que des mouvements orthogonaux de distance un, supprime le début de chacun, indexe le terrain, additionne chacun, prend le minimum, en soustrait un et vérifie que c'est inférieur à la vitesse.