Rundenbasierte Taktikspiele wie Advance Wars, Wargroove und Fire Emblem bestehen aus einem quadratischen Gitter mit unterschiedlichem Gelände und Einheiten unterschiedlicher Bewegungsklassen, die für jeden Geländetyp unterschiedliche Kosten erfordern. Wir werden eine Untergruppe dieses Problems untersuchen.

Herausforderung

Ihre Aufgabe ist es zu bestimmen, ob ein Ort von einem anderen aus erreichbar ist, wenn ein Raster von Geländekosten und eine Bewegungsgeschwindigkeit vorgegeben ist.

Einheiten können sich nur orthogonal bewegen, wenn die Kosten für das Bewegen auf ein Quadrat dem Wert der entsprechenden Zelle auf dem Gitter entsprechen (das Abheben ist kostenlos). Zum Beispiel kostet der Wechsel von einer Zelle mit dem Wert 3 zu einer Zelle mit dem Wert 1 1 Bewegung, der Wechsel in die andere Richtung erfordert 3 Bewegungen. Auf einige Felder kann möglicherweise nicht zugegriffen werden.

Beispiel

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

Um von [1]nach zu gelangen, <1>sind mindestens 7 Bewegungspunkte erforderlich, indem Sie ein Feld nach rechts und dann drei nach unten bewegen. Wenn also die Bewegungsgeschwindigkeit 6 oder weniger beträgt, sollten Sie eine falsche Antwort ausgeben.

Beispiel Testfälle

Bei diesen werden Koordinaten mit Nullindex (Zeile, Spalte) und nicht in eckigen Klammern angegeben, um das Parsen zu vereinfachen. Nicht erreichbare Zellen werden mit dargestelltX

Fall 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

Fall 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

Fall 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

Fall 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

Fall 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

Fall 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

Fall 3a

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

Output: False

Fall 3b

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

Output: True

Regeln, Annahmen und Hinweise

• Standardlücken sind verboten, I / O kann in jedem beliebigen Format vorliegen
• Sie können davon ausgehen, dass sich alle Koordinaten auf dem Raster befinden
• Die Bewegungsgeschwindigkeit wird niemals über 100 liegen
• Unzugängliche Zellen können mit sehr großen Zahlen (z. B. 420, 9001, 1 Million) oder mit 0 oder Null dargestellt werden, je nachdem, was für Sie am bequemsten ist.
• Alle Eingaben bestehen aus positiven Ganzzahlen (es sei denn, Sie verwenden Null oder 0, um nicht erreichbare Zellen darzustellen).

TSQL Abfrage, 205 191 Bytes

Die Eingabe ist eine Tabellenvariable @t

@ x = Start xpos, @ y = Start ypos @ i = Ende xpos, @ j = Ende ypos @ = Geschwindigkeit

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

Probieren Sie es online ungolfed version

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]

Probieren Sie es online!

Nimmt ein Array mvon ganzen Zahlen, wobei 'X'als larger-than-Wert 100 ;, einer Geschwindigkeit a, mmit der Breite wund die Höhe h; und gibt zurück, ob wir bei der mit Null indizierten Zeilen- / Spaltenzelle beginnen (r,c)und zur letzten Zelle gelangen können (R,C).

Der Algorithmus ist eine modifizierte Überflutung. Leicht ungolfter Code:

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 Byte

(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

Probieren Sie es online!

Kommentiert

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

Jelly , 59 Bytes

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

Probieren Sie es online!

Nicht furchtbar schnell; probiert alle Pfade aus, bis die Geschwindigkeitseinheiten erschöpft sind, und nimmt sogar die Schritte zurück. Dies vermeidet jedoch die Notwendigkeit zu überprüfen, ob Räume besucht werden. Die Eingabe erfolgt als[nrows, ncols],[start_row, start_col],[end_row, end_col],speed,flattened matrix column-major

Erläuterung

Hilfslink

+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

Hauptlink

ç             | 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

Jelly , 38 Bytes

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

Ein extrem ineffizientes Vollprogramm, das das Gelände akzeptiert (mit nicht sichtbaren Werten wie 101), dann koordiniert Start und Ende die Geschwindigkeit.

Probieren Sie es online! (Es macht nicht viel Sinn, die meisten Testfälle auszuprobieren!)

Wie?

Erstellt eine Liste aller Permutationen jeder Potenzmenge von "allen Geländepositionen mit Ausnahme von Start und Ende", umgibt jede mit Start und Ende, filtert nach denjenigen, die nur orthogonale Bewegungen der Entfernung eins ausführen, lässt den Start fallen von jedem Index geht es zurück in das Terrain, summiert jeden, nimmt das Minimum, subtrahiert eins und testet, dass dies weniger als die Geschwindigkeit ist.