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.