NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2001高中組決賽
 NPSC2001题目A

作者 主題: NPSC2001题目A  (閱讀 871 次)

abs2000

  • 新手
  • *
  • 文章數: 3
    • 檢視個人資料
NPSC2001题目A
« 於: 六月 05, 2013, 02:44:25 pm »

題目 A
坦克任務


輸入檔: tank.in / 輸出檔: tank.out

你是一名駕駛坦克的優秀指揮官。你的任務是深入敵營,躲過或是摧毀敵方重重砲臺的火力,成功抵達並摧毀敵方的基地。由於戰時的油料和砲彈都是珍貴的資源,你奉命利用衛星搜集來的地形資料,找到最短的路徑,並使用最少的砲彈完成此任務。
 
當你在砲臺所面對的方向時,你會瞬間被擊斃,因此你無法走入砲臺所面對的區域。但你可以先繞到砲臺所背對,或側對的區域,砲轟敵方的砲臺。而砲彈是無法穿過任何障礙物的。你的坦克和砲臺所發射的砲戰,只能朝正北,正東,正西,正南發射。當敵方砲臺被你摧毀時,砲臺的殘骸會留在原地,你的坦克無法直接通過。
若你一共走了a步,發出了b發砲彈,則你的任務是使a+b為最小。
輸入檔說明
每一筆測試資料,開頭兩個數字n,m,(n, m ³ 2) 分為表示此地圖的東西向,南北向的大小。接下來有m行,表示你所在的地方的地圖,地圖由 '  '(空白) 和 '*'(星號)所組成,空白表示你可以行走的路,星號是無法通過的地形,此地圖的最外一圈必定由星號所圍成。
 
接下來的四個數字start_x,start_y,destination_x,destination_y分別表示你的出發位置,和敵方基地的位置,地圖中最西北角的座標為(0,0)。再來1個數字num_of_enemy (0 <= num_of_enemy <=4) 表示地圖上敵方砲臺的數目.接下來有num_of_enemy組的(x,y,d),表示該砲臺的位置和面對的方向(方向N,E,S,W表示面對北,東,南,西),相對於地圖上(上,右,下,左)。
 
最後一筆測試資料的開頭包含兩個0, 此時程式應結束。
輸出檔說明
對每一筆測試資料,輸出一行,告訴你的長官你所預計花費的行動數
"MINIMAL STEPS: n." 其中n是行動數: a+b (走了a步+發出b發砲彈)
 
若你發現你已受困,則輸出"IMPOSSIBLE."
範例輸入
//P.S 可能输入的空格有点问题
6 6
******
*       *
***    *
****  *
*       *
******
1 1 1 4
1 4 1 S
6 6
******
*       *
****  *
****  *
*       *
******
1 1 1 4
1 4 4 N
0 0
範例輸出
MINIMAL STEPS: 10.
IMPOSSIBLE.
« 上次編輯: 六月 07, 2013, 09:40:20 am 由 abs2000 »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2001高中組決賽
 NPSC2001题目A