Universal Cup Judging System

Universal Cup

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

題目描述

你有一隻可愛的邦布(Bangboo),它正在參加「Marcel 的大冒險」。

這隻邦布在三維空間中移動。它的起點是 $(S_x, S_y, S_z)$,終點是 $(T_x, T_y, T_z)$。你可以將它視為一個以 $(S_x, S_y, S_z)$ 為中心的單位立方體。三維空間中存在 $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$ 行,每行包含三個整數 $x_i, y_i, z_i$($0 \le x_i, y_i, z_i \le 10^9$),表示第 $i$ 個障礙物的座標。保證在 $(S_x, S_y, S_z - 1)$ 和 $(T_x, T_y, T_z - 1)$ 處必須存在障礙物。

接下來的 $m$ 行,每行包含三個整數 $a_i, b_i, c_i$($|a_i|, |b_i|, |c_i| \le 10^9$),表示第 $i$ 種傳送方式。

對於每組測試資料,保證所有輸入的座標兩兩不同,且所有傳送方式兩兩不同。

保證所有測試資料的 $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.