1749 . [APIO '11] Path

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

tmwilliamlin
我的中文很爛

User's AC Ratio

57.1% (4/7)

Submission's AC Ratio

9.7% (6/62)

Tags

APIO 2011-APIO

Description

TooDee 是一塊二維格子狀的土地（就像著名的笛卡爾坐標系那樣），在這裡生活著很多可愛的 Dee。
Dee 是像蜜蜂一樣的小動物，它們只在二維活動，而且它們非常的文明開化。
TooDee 的蜂窩和正常世界的蜂窩也是很不一樣的，它們是矩形的且它們的邊平行於TooDee 的地理坐標系，
就是說矩形的邊或者是東西走向，或者是南北走向。

因為Dees 是很高級的生物，它們有很多固定的飛行軌道，
這些軌道由一些平行於坐標軸的線段組成，線段只會在經緯度都是整數的點相交。
Dee 在 TooDee飛行時必須遵守以下規則（請記住TooDee 中所有點的經緯度都是整數）：

※如果當前在點(XS, YS)，則下步只能飛到四個鄰點(XS, YS – 1), (XS, YS + 1),(XS – 1, YS ), (XS + 1, YS )；
※不可以進入蜂巢；
※只能在蜂巢的角或者邊上改變飛行方向；
※開始的時候可以向任何方向飛；

今晚是公共財政大臣Deeficer 的女兒的生日，她想儘早回家，請幫她找到最快的回家路徑。
假設她每秒可以飛行一個單位的距離。

Input Format

每個測試點包含多組數據。
輸入的第一行包含一個整數T，表示測試數據的組數。
接下來依次描述這 T組數據，相鄰的兩組之間使用一個空行分隔。測試數據不多於 20 組。

對於每組數據，第一行包含4 個整數xs, ys, xt, yt，
表示Deeficer 的辦公室和家的坐標分別為(xs, ys)和(xt, yt)。
第二行包含一個整數n，表示蜂巢的個數。
接下來的n 行描述所有的蜂巢，其中第i 行包含4 個整數xi1, yi1, xi2, yi2，
表示第i 個蜂巢兩個對角的坐標分別為(xi1, yi1)和(xi2, yi2)。

任何兩個蜂巢都不會相交，也不會接觸（在角上也不會接觸）。
辦公室和家處在不同的位置。每個蜂巢的面積為正。

對於20%的測試數據，n ≤ 10，所有的坐標都是小於100 的非負整數；
對於60%的測試數據，n ≤ 100，所有坐標的絕對值都小於1000；
對於100%的測試數據，1 ≤ n ≤ 1000，所有坐標都是不超過109 的整數；

Output Format

對於每一組數據，輸出一個整數，表示Deeficer 最快回家的時間（單位為秒），
如果她無法按規則回家，則輸出"No Path"（不含引號）。

Sample Input 1

2

1 7 7 8
2
2 5 3 8
4 10 6 7

2 1 5 4
1
3 1 4 3

Sample Output 1

9
No Path

Hints

Problem Source

原TIOJ1749 / APIO '11

Subtasks

No. Testdata Range Score
1 0 2
2 1 2
3 2 2
4 3 2
5 4 2
6 5 2
7 6 2
8 7 2
9 8 2
10 9 2
11 10 2
12 11 2
13 12 2
14 13 2
15 14 2
16 15 2
17 16 2
18 17 2
19 18 2
20 19 2
21 20 2
22 21 2
23 22 2
24 23 2
25 24 2
26 25 2
27 26 2
28 27 2
29 28 2
30 29 2
31 30 2
32 31 2
33 32 2
34 33 2
35 34 2
36 35 2
37 36 2
38 37 2
39 38 2
40 39 22

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11
11 2000 65536 262144 12
12 2000 65536 262144 13
13 2000 65536 262144 14
14 2000 65536 262144 15
15 2000 65536 262144 16
16 2000 65536 262144 17
17 2000 65536 262144 18
18 2000 65536 262144 19
19 2000 65536 262144 20
20 2000 65536 262144 21
21 2000 65536 262144 22
22 2000 65536 262144 23
23 2000 65536 262144 24
24 2000 65536 262144 25
25 2000 65536 262144 26
26 2000 65536 262144 27
27 2000 65536 262144 28
28 2000 65536 262144 29
29 2000 65536 262144 30
30 2000 65536 262144 31
31 2000 65536 262144 32
32 2000 65536 262144 33
33 2000 65536 262144 34
34 2000 65536 262144 35
35 2000 65536 262144 36
36 2000 65536 262144 37
37 2000 65536 262144 38
38 2000 65536 262144 39
39 2000 65536 262144 40
Submit
Back to Top