Universal Cup Judging System

Universal Cup

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

Mô tả bài toán

Bạn có một chú Bangboo đáng yêu, và chú đang tham gia vào "Cuộc đại phiêu lưu của Marcel".

Chú Bangboo này di chuyển trong không gian ba chiều. Điểm xuất phát của nó là $(S_x, S_y, S_z)$, và đích đến là $(T_x, T_y, T_z)$. Bạn có thể coi nó như một khối lập phương đơn vị có tâm tại $(S_x, S_y, S_z)$. Có $n$ chướng ngại vật trong không gian ba chiều, mỗi chướng ngại vật là một khối lập phương đơn vị có tâm tại $(x_i, y_i, z_i)$. Đảm bảo rằng tọa độ của điểm xuất phát, đích đến và tất cả các chướng ngại vật đôi một khác nhau, đồng thời tại $(S_x, S_y, S_z - 1)$ và $(T_x, T_y, T_z - 1)$ chắc chắn có chướng ngại vật.

Bangboo có thể dịch chuyển tức thời. Ở mỗi bước, nó có $m$ phương thức dịch chuyển khả dụng. Giả sử hiện tại nó đang ở $(x, y, z)$. Phương thức dịch chuyển thứ $i$ sẽ đưa nó tới $(x + a_i, y + b_i, z + c_i)$, sau đó nó sẽ rơi tự do. Một cách hình thức, nó sẽ dịch chuyển tới $(x + a_i, y + b_i, d)$, trong đó $d$ là giá trị lớn nhất thỏa mãn $d \le z + c_i$ và tại $(x + a_i, y + b_i, d - 1)$ có một chướng ngại vật. Nếu tại $(x + a_i, y + b_i, z + c_i)$ có chướng ngại vật, hoặc không tồn tại giá trị $d$ nào thỏa mãn, thì không thể thực hiện lần dịch chuyển này.

Mục tiêu của bạn là giúp Bangboo đi từ điểm xuất phát tới đích đến với số bước ít nhất. Nếu không thể tới được đích đến, hãy in ra $-1$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 500$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), lần lượt biểu thị số lượng chướng ngại vật và số lượng phương thức dịch chuyển mà Bangboo có thể dùng.

Dòng thứ hai chứa sáu số nguyên $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$), biểu thị điểm xuất phát và đích đến của Bangboo.

$n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), biểu thị tọa độ của chướng ngại vật thứ $i$. Đảm bảo rằng tại $(S_x, S_y, S_z - 1)$ và $(T_x, T_y, T_z - 1)$ chắc chắn có chướng ngại vật.

$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), biểu thị phương thức dịch chuyển thứ $i$.

Đối với mỗi bộ dữ liệu, đảm bảo rằng tất cả các tọa độ trong dữ liệu vào đôi một khác nhau, và tất cả các phương thức dịch chuyển đôi một khác nhau.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^3$, và tổng của $m$ trên tất cả các bộ dữ liệu không vượt quá $10^3$.

Kết quả

Đối với mỗi bộ dữ liệu, in ra một số nguyên duy nhất trên một dòng, biểu thị số bước ít nhất cần thiết để đi từ điểm xuất phát tới đích đến. Nếu không thể tới được đích đến, hãy in ra $-1$.

Ví dụ

Dữ liệu vào 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

Kết quả 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.