d070. 5.闖關遊戲 - 程式闖關解題系統

內容

真愛樂園裡最有人氣的，就是這個闖關遊戲了。在一個NxN的方形區域裡，每個格子是一個關卡，通過之後就可以到相鄰的其他格子。玩家們從左上角的格子出發，終點則是在右下角，由於通過每個格子的關卡要花費不同的點數，如果一開始沒有帶足夠的點數出發，則無法到達終點而闖關失敗。

因為從左上角到右下角有許多不同的走法，現在想請你找出從左上角到右下角闖關成功，最少要花費多少的點數。

輸入說明

輸入資料的第一行有一個正整數N (3<=N<=300)，代表這個方形區域由 NxN個格子組成。

接下來有N行，每行有N個1~1000的正整數，代表每個格子的關卡所需要花費的點數。

輸出說明

請輸出從左上角到右下角闖關成功所花費的最少點數是多少，包括左上角和右下角這兩關的點數。

範例輸入 #1

範例輸出 #1

範例輸入 #2

5
1 1 1 1 1
1000 1000 1000 1000 1
1 1 1 1 1
1 1000 1000 1000 1000
1 1 1 1 1

範例輸出 #2

測資資訊：

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

提示：

範例說明：

以範例2來說，沿著花費1的格子走下來，總花費就是17。

評分說明：

本題共有三個子題，分數及條件限制如下：

子題1(30分)：N<=10
子題2(30分)：N<=50
子題3(40分)：無限制

標籤:

BFS

出處:

中女112 [管理者：

sagit (sagit)

]

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