回分類題庫
h091: F.英雄Fantasy for you
關鍵字: NPSC 2011 高中組初賽

測資點 : 2 | Time Limit : 30000 ms | Memory Limit : 128000 KB
Accepted : 18 Times / 16 Users | Submit : 86 Times / 21 Users | Accepted rate : 76%
題目加入時間 : 2012-11-04 02:28

Content: 简体中文

英雄是一款線上遊戲,在這款遊戲中的地圖是以 N×N 的格子方式呈現。在一般的情況下,每次玩家只能往上、下、左、右四個方向移動一格。但是,在某些格子之中備有一些傳送門(如圖中有綠色點的格子),這個傳送門讓你也可以選擇要往左上、左下、右下和右上移動一格,也就是可以前往周圍八格。

現在你的公會被攻打了,你必須要趕到你的公會去幫忙,然而你在這個地圖的左上角(如圖中有紅色點的格子),而公會卻在右下角(如圖中有藍色點的格子)。幸運的是,你有所有傳送門的座標,你希望能夠妥善的利用傳送門讓你縮短到公會的時間。每次從一格移動到另一格則時間加一,你希望能夠用最短的時間到公會的位置。

Input:

輸入的第一行有一個正整數T,代表測試資料的組數(1<=T<=100)。

每一組測試資料的第一行有一個整數 N (1<=N<=10000000)。第二行有一個數字 K (0<=K<=50000),代表總共有幾個傳送門。第三行有 K 個數字 X1,X2,…,XK (1<=Xi<=N),代表這 K 個傳送門的 x 座標。第四行有 K 個數字 Y1,Y2,…,YK (1<=Yi<=N),代表這 K 個傳送門的 y 座標。座標從左上角開始算,左上角為(1,1)。

Output:

對每筆測試資料輸出一個整數,代表你要到公會所需的最短時間。
第一筆測資最短的走法如上圖。
第二筆測資最短的走法為 (1,1)→(2,1)→(3,2)→(4,3)→(4,4)。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
14
5
4 9 5 8 12
4 7 10 11 12
4
3
2 2 3
2 1 2

Sample Output :

22
4

Hint :

Author :

NPSC 2011 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum