Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Opis

Masz uroczego Bangboo, który bierze udział w „Wielkiej Przygodzie Marcela”.

Ten Bangboo porusza się w przestrzeni trójwymiarowej. Jego punktem startowym jest $(S_x, S_y, S_z)$, a punktem docelowym $(T_x, T_y, T_z)$. Możesz traktować go jako sześcian jednostkowy o środku w $(S_x, S_y, S_z)$. W przestrzeni trójwymiarowej znajduje się $n$ przeszkód, z których każda jest sześcianem jednostkowym o środku w $(x_i, y_i, z_i)$. Gwarantuje się, że współrzędne punktu startowego, punktu docelowego oraz wszystkich przeszkód są parami różne, a także że w $(S_x, S_y, S_z - 1)$ oraz $(T_x, T_y, T_z - 1)$ muszą znajdować się przeszkody.

Bangboo potrafi się teleportować. W każdym kroku ma do wyboru $m$ sposobów teleportacji. Załóżmy, że aktualnie znajduje się w $(x, y, z)$. $i$-ty sposób teleportacji przenosi go do $(x + a_i, y + b_i, z + c_i)$, po czym następuje swobodne spadanie. Formalnie, przeteleportuje się on do $(x + a_i, y + b_i, d)$, gdzie $d$ jest największą wartością spełniającą $d \le z + c_i$, dla której w $(x + a_i, y + b_i, d - 1)$ znajduje się przeszkoda. Jeśli w $(x + a_i, y + b_i, z + c_i)$ znajduje się przeszkoda lub takie $d$ nie istnieje, to tej teleportacji nie można wykonać.

Twoim celem jest sprawienie, aby Bangboo dotarł z punktu startowego do punktu docelowego w minimalnej liczbie kroków. Jeśli dotarcie do punktu docelowego jest niemożliwe, wypisz $-1$.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 500$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), oznaczające odpowiednio liczbę przeszkód oraz liczbę sposobów teleportacji dostępnych dla Bangboo.

Drugi wiersz zawiera sześć liczb całkowitych $S_x, S_y, S_z, T_x, T_y, T_z$ ($0 \le S_x, S_y, S_z, T_x, T_y, T_z \le 10^9$), oznaczających punkt startowy i punkt docelowy Bangboo.

Kolejne $n$ wierszy zawiera po trzy liczby całkowite $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), oznaczające współrzędne $i$-tej przeszkody. Gwarantuje się, że w $(S_x, S_y, S_z - 1)$ oraz $(T_x, T_y, T_z - 1)$ muszą znajdować się przeszkody.

Kolejne $m$ wierszy zawiera po trzy liczby całkowite $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), oznaczające $i$-ty sposób teleportacji.

Dla każdego przypadku testowego gwarantuje się, że wszystkie podane na wejściu współrzędne są parami różne oraz wszystkie sposoby teleportacji są parami różne.

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^3$, a suma $m$ po wszystkich przypadkach testowych nie przekracza $10^3$.

Wyjście

Dla każdego przypadku testowego wypisz w jednym wierszu jedną liczbę całkowitą oznaczającą minimalną liczbę kroków potrzebnych na dotarcie z punktu startowego do punktu docelowego. Jeśli dotarcie do punktu docelowego jest niemożliwe, wypisz $-1$.

Przykłady

Wejście 1

2
6 4
3 3 3 5 5 5
3 3 2
5 5 4
5 5 7
4 5 5
2 3 2
4 1 1
-1 0 3
2 -2 -1
1 4 9
1 0 0
3 2
0 0 1 1 1 1
0 0 0
1 1 0
1 1 2
1 1 1
1 1 2

Wyjście 1

5
-1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.