眾所皆知，OO峽谷為一個$H \times W$的網格圖。
某天大黑的朋友 ${log ({mid^{k}})}$ (一個玩家的ID)拿出了他最為擅長的角色「軋鎖」上陣，然而，身為一個平均OO聯盟玩家，他覺得正常玩遊戲實在是太無趣了，於是他想出了一種玩法：
「軋鎖」由$(S_x,S_y)$出發，他要以最少的滑行的次數到達敵方防禦塔$(T_x,T_y)$送出美味的人頭。
由於${log ({mid^{k}})}$拿到軋鎖會十分上頭，在每一次的滑行前，會從「上、下、左、右」決定一個方向瘋狂開滑。
一旦滑到超出峽谷邊界他就會掉進OO深淵，如此一來就無法達成送頭的目的。
為此他決定先在峽谷$H \times W$的範圍內的座標$(X_i, Y_i)$處設置$K$個障礙物(風牆)，只要軋鎖在滑的過程中撞到障礙物，他就會停在撞到障礙物之前的那一格。
特別注意到防禦塔並不是障礙物，且防禦塔只有一個。
由於如今${log ({mid^{k}})}$被困於得O者而分身乏術，所以想請身為他好朋友的你告訴他最少滑幾次能恰好停在防禦塔上！
萬一無論如何${log ({mid^{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\le t\le 4$
$1\le H, W\le 10^9$
$1\le S_x, T_x \le H$
$1\le S_y, T_y \le W$
$1\le K\le min(H * W - 2, 10^5)$
$1\le X_i \le H$
$1\le Y_i \le 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." (不含雙引號)
2 7 8 7 3 4 5 6 1 4 2 1 2 8 4 5 5 7 6 2 6 6 1 10 1 1 5 1 1 1 7
4 Guan Hao Ni Zhi Ji.
子題1 50pt
$1\le H, W \le 1000$
子題2 50pt
原題
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||