回分類題庫
z131: B.勇者傳說
關鍵字: 2012 NPSC 國中組 初賽

測資點 : 1 | Time Limit : 1000 ms | Memory Limit : 128000 KB
Accepted : 8 Times / 7 Users | Submit : 89 Times / 8 Users | Accepted rate : 88%
題目加入時間 : 2021-07-19 17:33

Content: 简体中文

原始題目網址:
https://contest.cc.ntu.edu.tw/npsc2012/teamclient/npsc2012junior.pdf
  胖胖天最近迷上了一款由 NPSC 公司(NPSC.com)在 2012 年推出的電玩遊戲---「勇者傳說」,這款遊戲十分有趣,你要操控勇者前往異世界打倒魔王,拯救世界。
  隨著胖胖天的努力,他的人物終於來到了一百等,也就是眾多玩家們所景仰的「滿等」,血量也達到了 100 滴血這麼多,真正的成為了勇者!
  終於胖胖天來到了遊戲的最後關卡-「魔王迷宮」,要來挑戰最終的大魔王了!
  「魔王迷宮」是一個由 N × N 的地板所組成的,魔王將左下角的地板編號為 (0, 0),右上角的地板編號為 (N − 1, N − 1) ,依此類推。勇者一開始降落於左下角的地板,目標是前往右上角的地板打倒魔王。但可怕的是,在迷宮中每前進一個地板(並消耗一單位的時間),血量就會減少一個單位!為了避免這樣的情形,胖胖天特地帶了 K 個「補命寶丸」,雖然使用會消耗一單位的時間 (不扣血),但是卻可以讓自己的角色補滿血!
  此外,魔王還在迷宮中設置了一些障礙物,一旦碰觸到這些障礙物,就會發生非常可怕的事情!所以絕對不可以碰到這些障礙物。但是,如果最左下角的地板或是右上角的地板一開始就有障礙物了,那胖胖天就肯定沒辦法達成目標!
  雖然胖胖天很厲害,但是他肚子餓了,想要早點打倒魔王,究竟胖胖天要花多久的時間才能抵達右上角的地板並且打倒魔王呢? 

Input:

  檔案的第一行有一個正整數 T(T ≤ 60) 表示接下來總共有幾筆測試資料。
  每一筆測試資料的第一行有一個正整數 N 以及兩個整數 M, K 分別以一個空白隔開,N 代表迷宮的大小、M 代表障礙物的數量、K 代表「補命寶丸」的數量。接下來有 M 行,每行有兩個數字 xi , yi ,代表 (xi , yi) 座標上的地板被魔王放置了障礙物。
  我們保證 N ≤ 100, M ≤ 5000, K ≤ 5。 

Output:

  對每筆測試資料輸出一行,每行包含一個整數,代表胖胖天抵達右上角的地板需要的時間,若無法抵達右上角的地板,請輸出 “-1”(不含引號)。

Sample Input:help

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

Sample Output :

2
16

Hint :

範例說明:
第一筆測試資料中,胖胖天分別向右及向上前進,花費了 2 單位的時間。
第二筆測試資料中,向上前進四格地板,向右前進兩格地板,向下前進四格地板,向右前進兩格地板,最後再向上前進四格地板,花費了 16 單位的時間。

Author :

2012 NPSC 國中組 初賽 (管理員:wubaie)

  Solve it!   Status Forum