Gim taktik berbasis giliran seperti Advance Wars, Wargroove, dan Fire Emblem terdiri dari kotak persegi dari berbagai medan dengan unit kelas gerakan berbeda yang membutuhkan biaya berbeda untuk setiap jenis medan. Kami akan menyelidiki sebagian masalah itu.

Tantangan

Tugas Anda adalah menentukan apakah satu lokasi dapat dijangkau dari yang lain mengingat kisi-kisi biaya medan dan kecepatan gerakan.

Unit hanya bisa bergerak secara orthogonal di mana biaya untuk pindah ke kotak adalah nilai sel yang sesuai pada kotak (pemindahan gratis). Misalnya, pindah dari sel yang bernilai 3 ke sel yang dihargai 1 membutuhkan 1 gerakan, tetapi sebaliknya membutuhkan 3. Beberapa kotak mungkin tidak dapat diakses.

Contoh

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

Pindah dari [1]ke <1>membutuhkan minimal 7 poin gerakan dengan bergerak ke kanan satu kotak dan kemudian turun tiga. Jadi, jika diberikan 6 atau kurang dari kecepatan gerakan, Anda harus menampilkan jawaban yang salah.

Contoh Kasus Uji

Ini akan menggunakan koordinat nol-indeks (baris, kolom) asal-kiri asal daripada sel kurung untuk memulai dan mengakhiri untuk membuat parsing lebih mudah. Sel yang tidak terjangkau akan diwakili denganX

Kasus 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

Kasus 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

Kasus 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

Kasus 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

Kasus 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

Kasus 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

Kasus 3a

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

Output: False

Kasus 3b

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

Output: True

Aturan, Asumsi, dan Catatan

• Celah standar dilarang, I / O bisa dalam format apa pun yang nyaman
• Anda dapat mengasumsikan koordinat semuanya ada di grid
• Kecepatan gerakan tidak akan pernah lebih dari 100
• Sel yang tidak dapat diakses dapat direpresentasikan dengan jumlah yang sangat besar (mis. 420, 9001, 1 juta) atau dengan 0 atau nol, yang mana yang paling nyaman bagi Anda.
• Semua input akan terdiri dari bilangan bulat positif (kecuali jika menggunakan nol atau 0 untuk mewakili sel yang tidak terjangkau)

Permintaan TSQL, 205 191 byte

Input adalah variabel tabel @t

@ x = mulai xpos, @ y = mulai ypos @ i = end xpos, @ j = end ypos @ = kecepatan

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

Cobalah secara online versi ungolfed

Python 2 , 220 byte

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]

Cobalah online!

Mengambil array mbilangan bulat, dengan 'X'nilai lebih besar dari 100; kecepatan a, mmemiliki lebar wdan tinggi h; dan kembali ketika kita bisa mulai di baris / kolom sel nol diindeks (r,c)dan sampai ke sel terakhir (R,C).

Algoritma ini adalah pengisian banjir yang dimodifikasi. Kode sedikit ungolfed:

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

Mengambil input sebagai (matrix)([endRow, endCol])(speed, startRow, startCol). Mengharapkan nilai besar untuk kotak yang tidak terjangkau. Mengembalikan atau .$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

Cobalah online!

Berkomentar

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 byte

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

Cobalah online!

Tidak terlalu cepat; mencoba semua jalur sampai unit kecepatan habis, bahkan menelusuri kembali langkah-langkahnya. Namun, ini menghindari kebutuhan untuk memeriksa apakah ruang dikunjungi. Input diberikan sebagai[nrows, ncols],[start_row, start_col],[end_row, end_col],speed,flattened matrix column-major

Penjelasan

Tautan pembantu

+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

Tautan utama

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

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

Program penuh yang sangat tidak efisien menerima medan (dengan unvisitables sebagai 101) kemudian mulai dan berakhir mengoordinasikan kemudian kecepatan.

Cobalah online! (tidak banyak gunanya mencoba sebagian besar kasus uji!)

Bagaimana?

Membuat daftar semua permutasi dari masing-masing set daya dari "semua lokasi medan kecuali awal & akhir", mengelilingi masing-masing dengan permulaan & akhir, filter untuk yang membuat hanya langkah orthogonal jarak satu, menjatuhkan awal dari masing-masing, indeks kembali ke medan, jumlah masing-masing, mengambil minimum, kurangi satu dan tes bahwa ini kurang dari kecepatan.