Turowe gry taktyczne, takie jak Advance Wars, Wargroove i Fire Emblem, składają się z kwadratowej siatki o zróżnicowanym terenie z jednostkami o różnych klasach ruchu, wymagającymi różnych kosztów dla każdego rodzaju terenu. Będziemy badać podzbiór tego problemu.
Wyzwanie
Twoim zadaniem jest ustalenie, czy do jednej lokalizacji można dotrzeć z innej, biorąc pod uwagę siatkę kosztów terenu i prędkość ruchu.
Jednostki mogą poruszać się ortogonalnie tylko wtedy, gdy koszt przejścia na kwadrat jest wartością odpowiedniej komórki na siatce (ruszenie jest bezpłatne). Na przykład przejście z komórki o wartości 3 na komórkę o wartości 1 kosztuje 1 ruch, ale przejście w drugą stronę wymaga 3. Niektóre kwadraty mogą być niedostępne.
Przykład
1 [1] 1 1 1
1 2 2 3 1
2 3 3 3 4
1 3 <1> 3 4
Przejście z [1]do <1>wymaga minimum 7 punktów ruchu, przesuwając się w prawo o jedno pole, a następnie o trzy w dół. Tak więc, jeśli podano 6 lub mniej jako prędkość ruchu, powinieneś dać odpowiedź fałszywą.
Przykładowe przypadki testowe
Będą one używać współrzędnych zero-indeksowanych od lewej do góry (wiersz, kolumna) zamiast komórek w nawiasach początkowych i końcowych, aby ułatwić analizę. Nieosiągalne komórki będą reprezentowane przezX
Przypadek 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
Przypadek 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
Przypadek 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
Przypadek 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
Przypadek 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
Przypadek 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
Przypadek 3a
2 1 1 2
2 3 3 1
Speed: 3
From (0, 0) to (1, 1)
Output: False
Przypadek 3b
2 1 1 2
2 3 3 1
Speed: 3
From (1, 1) to (0, 0)
Output: True
Reguły, założenia i uwagi
- Standardowe luki są zabronione, wejścia / wyjścia mogą mieć dowolny dogodny format
- Możesz założyć, że wszystkie współrzędne są na siatce
- Prędkość ruchu nigdy nie przekroczy 100
- Niedostępne komórki mogą być reprezentowane przez bardzo duże liczby (np. 420, 9001, 1 milion) lub przez 0 lub zero, w zależności od tego, co jest dla ciebie najwygodniejsze.
- Wszystkie dane wejściowe będą składać się z dodatnich liczb całkowitych (chyba że użyjemy null lub 0 do reprezentowania nieosiągalnych komórek)