Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Beschreibung

Sie haben einen niedlichen Bangboo, der an „Marcels großem Abenteuer“ teilnimmt.

Dieser Bangboo bewegt sich im dreidimensionalen Raum. Sein Startpunkt ist $(S_x, S_y, S_z)$ und sein Ziel ist $(T_x, T_y, T_z)$. Sie können ihn als einen Einheitswürfel betrachten, dessen Mittelpunkt bei $(S_x, S_y, S_z)$ liegt. Im dreidimensionalen Raum gibt es $n$ Hindernisse, von denen jedes ein Einheitswürfel mit Mittelpunkt bei $(x_i, y_i, z_i)$ ist. Es wird garantiert, dass die Koordinaten des Startpunkts, des Ziels und aller Hindernisse paarweise verschieden sind und dass sich bei $(S_x, S_y, S_z - 1)$ und $(T_x, T_y, T_z - 1)$ zwingend Hindernisse befinden.

Der Bangboo kann sich teleportieren. In jedem Schritt stehen ihm $m$ Teleportationsmethoden zur Verfügung. Angenommen, er befindet sich aktuell bei $(x, y, z)$. Die $i$-te Teleportationsmethode bringt ihn nach $(x + a_i, y + b_i, z + c_i)$, woraufhin er sich im freien Fall befindet. Formal teleportiert er sich nach $(x + a_i, y + b_i, d)$, wobei $d$ der maximale Wert ist, der $d \le z + c_i$ erfüllt und für den sich bei $(x + a_i, y + b_i, d - 1)$ ein Hindernis befindet. Falls sich bei $(x + a_i, y + b_i, z + c_i)$ ein Hindernis befindet oder kein solches $d$ existiert, kann diese Teleportation nicht durchgeführt werden.

Ihr Ziel ist es, den Bangboo vom Startpunkt aus mit der minimalen Anzahl an Schritten zum Ziel zu bringen. Falls es unmöglich ist, das Ziel zu erreichen, geben Sie $-1$ aus.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 500$), die die Anzahl der Testfälle angibt.

Für jeden Testfall:

Die erste Zeile enthält zwei ganze Zahlen $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), die die Anzahl der Hindernisse bzw. die Anzahl der dem Bangboo zur Verfügung stehenden Teleportationsmethoden angeben.

Die zweite Zeile enthält sechs ganze Zahlen $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$), die den Startpunkt und das Ziel des Bangboo angeben.

Die nächsten $n$ Zeilen enthalten jeweils drei ganze Zahlen $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), die die Koordinaten des $i$-ten Hindernisses angeben. Es wird garantiert, dass sich bei $(S_x, S_y, S_z - 1)$ und $(T_x, T_y, T_z - 1)$ zwingend Hindernisse befinden.

Die nächsten $m$ Zeilen enthalten jeweils drei ganze Zahlen $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), die die $i$-te Teleportationsmethode angeben.

Für jeden Testfall wird garantiert, dass alle eingegebenen Koordinaten paarweise verschieden sind und alle Teleportationsmethoden paarweise verschieden sind.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^3$ nicht überschreitet und die Summe von $m$ über alle Testfälle $10^3$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall in einer Zeile eine einzige ganze Zahl aus, die die minimale Anzahl an Schritten angibt, um vom Startpunkt zum Ziel zu gelangen. Falls es unmöglich ist, das Ziel zu erreichen, geben Sie $-1$ aus.

Beispiele

Eingabe 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

Ausgabe 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.