d793-acm-929-NumberMaze

zerojudge連結 http://zerojudge.tw/ShowProblem?problemid=d793

內容 ：

如下，數字迷宮為一個二維的數字 (0-9) 陣列。你可以用直角方向 (東、西、南、北) 在迷宮中尋訪。假設每一格的數字代表造訪該格的成本，那麼求出從入口走到出口所需的最小成本不見得很容易哦。

給你一 N×M (1 <= N,M <= 999) 的數字迷宮，你必須求出從左上角走到右下角所需的最小成本。上面範例的解答為 24。

輸入說明 ：

輸入檔含有數個迷宮。第一行含有一個正整數表示以下有幾個迷宮。每個迷宮的第一行為列數 N，第二行為行數 M，接下來 N 行每行代表迷宮的一行，含有以空白隔開的迷宮數字。

輸出說明 ：

對於每個迷宮，請輸出所需的最小值於一行。

範例輸入 ：

2

4

5

0 3 1 2 9

7 3 4 9 9

1 7 5 5 3

2 3 4 2 5

1

6

0 1 2 3 4 5

範例輸出 ：

24

15

提示 ：

出處 ：

UVa ACM 929 (管理：snail)

解題策略

Dijkstra演算法