a207. Q4找出總得分最少的路徑

內容

一個 10 × 10 棋盤如下圖，其座標依照以列為主(row major)的順序排列，依序為
[0,0],[0,1],[0,2],...,[9,8],[9,9]，左上角的[0,0]為入口，右下角的[9,9]為出口。

請從 10×10 棋盤的左上角入口，找一條路徑走到右下角出口，此路徑只能走相鄰的棋盤格子，也就是每個格子都只能往上、下、左、右四個格子走。

每個棋盤格子上都有一個分數，請找出從入口走到出口，走過格子的得分加總為最少之路徑。

請輸出最少總得分為多少，再依序輸出此路徑，從座標[0,0]開始到[9,9]結束。

輸入說明

輸入 100 個整數，所有整數值介於 0 到 500 之間，以空格隔開。此 100 個整數依序為棋盤格子座標[0,0], [0,1], [0,2],...,[9,8],[9,9]上的分數，按照以列為主(row major)的順序排列。

輸出說明

先輸出最少總得分的值，其資料型態為整數，再依序輸出此路徑的所有座標值。

座標值的輸出格式為 [整數,整數]，所有值之間皆以逗號隔開。

範例輸入 #1

60 25 40 10 35 15 10 25 10 20 75 170 145 75 10 260 110 40 25 15 95 15 20 30 50 175 20 10 225 30 15 20 95 185 280 170 90 185 20 215 20 100 90 70 50 80 30 10 175 255 45 255 10 120 100 210 290 235 190 185 115 185 25 195 40 15 125 260 175 55 10 30 185 60 20 150 95 30 60 10 40 160 55 25 10 205 20 55 30 10 60 90 100 10 170 10 15 40 80 50

範例輸出 #1

1070,[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[1,7],[2,7],[2,6],[3,6],[4,6],[4,5],[4,4],[5,4],[6,4],[7,4],[8,4],[9,4],[9,5],[9,6],[8,6],[8,7],[8,8],[8,9],[9,9]

測資資訊：

記憶體限制： 128 MB
不公開測資點#0 (10%): 1.0s , <1K
不公開測資點#1 (10%): 1.0s , <1K
不公開測資點#2 (10%): 1.0s , <1K
不公開測資點#3 (10%): 1.0s , <1K
不公開測資點#4 (10%): 1.0s , <1K
不公開測資點#5 (10%): 1.0s , <1K
不公開測資點#6 (10%): 1.0s , <1K
不公開測資點#7 (10%): 1.0s , <1K
不公開測資點#8 (10%): 1.0s , <1K
不公開測資點#9 (10%): 1.0s , <1K

提示：

標籤:

graph greedy 最短路徑

出處:

110彰雲嘉資訊學科 Q4 [管理者：

911091@stu.c... (17莊明達 David)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」