Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

Deskripsi

Anda memiliki seekor Bangboo yang lucu, dan ia sedang berpartisipasi dalam "Petualangan Besar Marcel".

Bangboo ini bergerak di dalam ruang tiga dimensi. Titik awalnya adalah $(S_x, S_y, S_z)$, dan tujuannya adalah $(T_x, T_y, T_z)$. Anda dapat menganggapnya sebagai sebuah kubus satuan yang berpusat di $(S_x, S_y, S_z)$. Terdapat $n$ rintangan di dalam ruang tiga dimensi tersebut, yang masing-masing merupakan sebuah kubus satuan yang berpusat di $(x_i, y_i, z_i)$. Dijamin bahwa koordinat titik awal, tujuan, dan semua rintangan saling berbeda satu sama lain, serta pasti terdapat rintangan di $(S_x, S_y, S_z - 1)$ dan $(T_x, T_y, T_z - 1)$.

Bangboo dapat melakukan teleportasi. Pada setiap langkah, ia memiliki $m$ metode teleportasi yang tersedia. Misalkan saat ini ia berada di $(x, y, z)$. Metode teleportasi ke-$i$ akan mengirimnya ke $(x + a_i, y + b_i, z + c_i)$, yang kemudian diikuti dengan jatuh bebas. Secara formal, ia akan berteleportasi ke $(x + a_i, y + b_i, d)$, di mana $d$ adalah nilai maksimum yang memenuhi $d \le z + c_i$ dan terdapat rintangan di $(x + a_i, y + b_i, d - 1)$. Jika terdapat rintangan di $(x + a_i, y + b_i, z + c_i)$, atau jika tidak ada nilai $d$ yang memenuhi syarat, maka teleportasi ini tidak dapat dilakukan.

Tujuan Anda adalah membuat Bangboo mencapai tujuan dari titik awal dengan menggunakan jumlah langkah minimum. Jika tidak mungkin mencapai tujuan, keluarkan $-1$.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 500$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), yang masing-masing menyatakan banyaknya rintangan dan banyaknya metode teleportasi yang tersedia bagi Bangboo.

Baris kedua berisi enam bilangan bulat $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$), yang menyatakan titik awal dan tujuan Bangboo.

$n$ baris berikutnya masing-masing berisi tiga bilangan bulat $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), yang menyatakan koordinat rintangan ke-$i$. Dijamin bahwa pasti terdapat rintangan di $(S_x, S_y, S_z - 1)$ dan $(T_x, T_y, T_z - 1)$.

$m$ baris berikutnya masing-masing berisi tiga bilangan bulat $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), yang menyatakan metode teleportasi ke-$i$.

Untuk setiap kasus uji, dijamin bahwa semua koordinat masukan saling berbeda satu sama lain, dan semua metode teleportasi saling berbeda satu sama lain.

Dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $10^3$, dan jumlah dari $m$ di seluruh kasus uji tidak melebihi $10^3$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat pada satu baris, yang menyatakan jumlah langkah minimum yang diperlukan untuk mencapai tujuan dari titik awal. Jika tidak mungkin mencapai tujuan, keluarkan $-1$.

Contoh

Masukan 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

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