參考 題型範例 - 全國高級中等學校技藝競賽平台 工業類

題目:大地遊戲闖關


問題描述
    小青擔任 T 大迎新宿營大地遊戲 A 小隊隊長,此大地遊戲中,設有許多遊戲關卡,然而關卡和路途嚴峻,可能會遇到無法通行的情況。



    上圖是某一大地遊戲7個關卡的分布情況,遊戲關卡使用不同數字(其值大於 1 並小於 30)標記,而關卡與關卡之間的數值(大於 0.0),代表路途上險峻的程度,每條路線僅能通行一次,箭頭代表通行方向,每一個箭頭代表一條路線,例如關卡 6 到關卡 2 之間有兩條路線。 
    在給定起始關卡和終點關卡後,身為小隊長的小青,要評估如何走那些路線?才能夠順利且最快的闖關成功。 
例1:從關卡 1(起始)到關卡 4(終點)只有一條路線(1->3->4),所以可以順利完成闖關(至少有一條路線可以連結起始關卡和終點關卡),此路途險峻程度為 0.8 + 0.5 = 1.3。 
例2:從關卡 1(起始)到關卡 2(終點)則有兩種路線:(1->6->2),其路途險峻程度為 0.5 + 0.6 = 1.1,以及(1->2),其路途險峻程度為 0.2;小青隊長為了順利且最快的闖關成功,所以,她要選關卡1直接到關卡 2,減少路途險峻進而順利闖關成功。
例3:從關卡 1(起始)到關卡 7(終點)則有七種路線,其中線路 1->6->7,路途險峻程度1 為最低,所以,小青會選此路線,而不選其他六條路線。 
請你(妳)幫小青寫一程式,幫助小青做明智路線抉擇,才能夠順利且最快的闖關成功。 

大地遊戲關卡文字檔: 
在輸入的第 1 列(Row)為大地遊戲關卡的數目X;接下來第 2 列到第 X+1 列代表一個 X*X 陣列,陣列的第 m 列(Row) (即輸入的第 m+1 列)的每一數值代表某一編號為 m 的關卡到其它關卡(1至X)間存有一條路線直接連接它們並可通行的險峻程度;輸入檔的最後一列(第 X+2 列)有兩個不同的數值,分別由左至右代表大地遊戲的起始關卡與終點關卡。任一兩數字之間都用一個空白隔開。以上圖為例,輸入的大地遊戲關卡文字檔內容如下: 
7
0.0 0.2 0.8 0.0 0.0 0.5 0.0
0.0 0.0 0.0 0.0 0.7 0.6 0.0
0.0 0.0 0.0 0.5 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.9 0.0 0.4
0.0 0.0 0.0 0.0 0.0 0.0 0.2
0.0 0.9 0.0 0.0 0.0 0.0 0.5
0.0 0.0 0.0 0.0 0.0 0.0 0.0
1 4
  此大地遊戲關卡文字檔內容第一列為 7,表示大地遊戲關卡的數目為 7,接下來第 2 列到第 8 列代表一個 7*7 陣列,陣列的第 1 列(Row)和第 2 行(Column)的值為 0.2,這表示關卡 1 到關卡 2 路途險峻程度為 0.2;輸入檔的最後一列(第 9 列)有兩個不同的數值,分別表示大地遊戲的起始關卡 1 與終點關卡 4。
程式功能要求:
請利用上述說明和範例,寫一個程式,能完成以下功能要求:
(1) 能讓小青選擇輸入大地遊戲關卡文字檔(1 < 遊戲關卡數目 < 30)。
(2) 能將小青所輸入的大地遊戲關卡文字檔內容顯示出來。
(3) 能顯示最快的闖關路線,並顯示路途險峻程度。
程式執行例 1: 



程式執行例 2:


若妳(你)的程式都完成上述功能和要求,才可以上傳要求檢查功能。

輸入格式輸出格式



範例一
輸入正確輸出



執行結果


範例二
輸入正確輸出



執行結果


範例三
輸入正確輸出



執行結果


     程式碼下載