o376. 滑起來咯寶貝 - 高中生程式解題系統

內容

眾所皆知，OO峽谷為一個 $H \times W$ 的網格圖。

某天大黑的朋友 $l o g (m i d^{k})$ (一個玩家的ID)拿出了他最為擅長的角色「軋鎖」上陣，然而，身為一個平均OO聯盟玩家，他覺得正常玩遊戲實在是太無趣了，於是他想出了一種玩法：

「軋鎖」由 $(S_{x}, S_{y})$ 出發，他要以最少的滑行的次數到達敵方防禦塔 $(T_{x}, T_{y})$ 送出美味的人頭。

由於 $l o g (m i d^{k})$ 拿到軋鎖會十分上頭，在每一次的滑行前，會從「上、下、左、右」決定一個方向瘋狂開滑。

一旦滑到超出峽谷邊界他就會掉進OO深淵，如此一來就無法達成送頭的目的。

為此他決定先在峽谷 $H \times W$ 的範圍內的座標 $(X_{i}, Y_{i})$ 處設置 $K$ 個障礙物(風牆)，只要軋鎖在滑的過程中撞到障礙物，他就會停在撞到障礙物之前的那一格。

特別注意到防禦塔並不是障礙物，且防禦塔只有一個。

由於如今 $l o g (m i d^{k})$ 被困於得O者而分身乏術，所以想請身為他好朋友的你告訴他最少滑幾次能恰好停在防禦塔上！

萬一無論如何 $l o g (m i d^{k})$ 都無法達成目標的話，請跟他說"Guan Hao Ni Zhi Ji."。

輸入說明

第一行有一個數字 $t$ 代表測資的數量

每筆測資中:
第一行有三個數字 $H$ $W$ $K$ 如題序所述
第二行有兩個數字 $S . x$ $S . y$ 代表起點S的x, y座標
第三行有兩個數字 $T . x$ $T . y$ 代表目標防禦塔T的x, y座標
接下來有K行 $X_{i}$ $Y_{i}$ 代表障礙物的x, y座標

$1 \leq t \leq 4$

$1 \leq H, W \leq 10^{9}$
$1 \leq S_{x}, T_{x} \leq H$
$1 \leq S_{y}, T_{y} \leq W$
$1 \leq K \leq m i n (H * W - 2, 10^{5})$
$1 \leq X_{i} \leq H$
$1 \leq Y_{i} \leq W$
$(S_{x}, S_{y}) \neq (T_{x}, T_{y})$
$(S_{x}, S_{y}) \neq (X_{i}, Y_{i})$
$(S_{x}, S_{y}) \neq (X_{i}, Y_{i})$

如果 $i \neq j$ 那麼 $(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$

輸出說明

若能成功送頭，輸出移動到目標的最短移動次數。

否則輸出"Guan Hao Ni Zhi Ji." (不含雙引號)

範例輸入 #1

範例輸出 #1

4
Guan Hao Ni Zhi Ji.

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (50%): 2.0s , <1M
公開測資點#1 (3%): 1.0s , <1M
公開測資點#2 (3%): 1.0s , <1M
公開測資點#3 (3%): 1.0s , <1M
公開測資點#4 (3%): 1.0s , <10M
公開測資點#5 (3%): 1.0s , <1M
公開測資點#6 (3%): 1.0s , <10M
公開測資點#7 (4%): 1.0s , <10M
公開測資點#8 (4%): 1.0s , <1M
公開測資點#9 (4%): 1.0s , <1M
公開測資點#10 (4%): 1.0s , <10M
公開測資點#11 (4%): 1.0s , <10M
公開測資點#12 (4%): 1.0s , <10M
公開測資點#13 (4%): 1.0s , <1M
公開測資點#14 (4%): 1.0s , <10M

提示：

子題1 50pt
$1 \leq H, W \leq 1000$

子題2 50pt

原題

標籤:

出處:

[管理者： CGSH (快加油吧~~) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」