Universal Cup Judging System

Universal Cup

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

문제 설명

당신에게는 귀여운 방부(Bangboo)가 한 마리 있으며, 이 방부는 "마르셀의 대모험"에 참가하고 있습니다.

이 방부는 3차원 공간에서 이동합니다. 시작점은 $(S_x, S_y, S_z)$이고 도착점은 $(T_x, T_y, T_z)$입니다. 방부는 $(S_x, S_y, S_z)$를 중심으로 하는 단위 정육면체로 간주할 수 있습니다. 3차원 공간에는 $n$개의 장애물이 있으며, 각 장애물은 $(x_i, y_i, z_i)$를 중심으로 하는 단위 정육면체입니다. 시작점, 도착점 및 모든 장애물의 좌표는 서로 다름이 보장되며, $(S_x, S_y, S_z - 1)$과 $(T_x, T_y, T_z - 1)$에는 반드시 장애물이 존재합니다.

방부는 순간이동을 할 수 있습니다. 각 단계에서 $m$가지의 순간이동 방법을 사용할 수 있습니다. 현재 $(x, y, z)$에 있다고 가정합시다. $i$번째 순간이동 방법은 방부를 $(x + a_i, y + b_i, z + c_i)$로 보내며, 그 후 자유 낙하를 합니다. 엄밀하게 말하면, 방부는 $(x + a_i, y + b_i, d)$로 순간이동하는데, 여기서 $d$는 $d \le z + c_i$를 만족하고 $(x + a_i, y + b_i, d - 1)$에 장애물이 존재하는 최댓값입니다. 만약 $(x + a_i, y + b_i, z + c_i)$에 장애물이 있거나 조건을 만족하는 $d$가 존재하지 않으면 이 순간이동은 수행할 수 없습니다.

당신의 목표는 방부가 시작점에서 출발하여 최소 단계 수로 도착점에 도달하게 하는 것입니다. 도착점에 도달할 수 없다면 $-1$을 출력하세요.

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 500$)가 주어집니다.

각 테스트 케이스에 대하여:

첫 번째 줄에는 장애물의 수와 방부가 사용할 수 있는 순간이동 방법의 수를 나타내는 두 정수 $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$)이 주어집니다.

두 번째 줄에는 방부의 시작점과 도착점을 나타내는 여섯 개의 정수 $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$)가 주어집니다.

다음 $n$개의 줄에는 각각 $i$번째 장애물의 좌표를 나타내는 세 정수 $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$)가 주어집니다. $(S_x, S_y, S_z - 1)$과 $(T_x, T_y, T_z - 1)$에는 반드시 장애물이 존재함이 보장됩니다.

다음 $m$개의 줄에는 각각 $i$번째 순간이동 방법을 나타내는 세 정수 $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$)가 주어집니다.

각 테스트 케이스에 대해 입력으로 주어지는 모든 좌표는 서로 다르며, 모든 순간이동 방법도 서로 다름이 보장됩니다.

모든 테스트 케이스에서 $n$의 합은 $10^3$을 넘지 않으며, $m$의 합도 $10^3$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 시작점에서 도착점에 도달하는 데 필요한 최소 단계 수를 나타내는 정수를 한 줄에 출력합니다. 도착점에 도달할 수 없다면 $-1$을 출력합니다.

예제

예제 입력 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

예제 출력 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.