P-7-3. 機器人走棋盤 (APCS 201906)
有一個方格棋盤的每一個格子裡都標示了一個不同的整數,有一個機器人在此方格棋盤上行動,
每一次只會移動到目前位置的上下左右四個相鄰格子其中之一。起點是數字最小的格子,每次移動則在可以移動位置中挑選數字最小的格子
,但是走過的格子就不會再走,當無路可走的時候,機器人就會停下來。輸入方格棋盤中每個格子的數字,
請模擬機器人走過的路徑,並輸出機器人走過的格子的數字總和。
以下是一個例子,輸入的 4*5 的方格內的數字如圖中所標示。在本例子中,機器人的起點會是 1,
所走的路徑是 1 -> 4 -> 6 -> 7 -> 14 -> 20 -> 21 -> 29 -> 30。
走到 30 的時候已經無路可走,所以機器人就停止了,而經過的數字總和是 132。
範例: 24 7 14 20 30 11 6 4 21 29 2 8 1 35 40 3 9 5 12 15
輸入格式
輸入的第一行是兩個不超過 100 的正整數 m 與 n,代表是一個 m*n 的方格棋盤, 接下來有 m 行,每行 n 個數字,分別是方格棋盤由上而下,由左而右的數字。 方格內的數字皆為不超過 1e5 的非負整數,同一行數字之間以空白間隔。
輸出格式
機器人走過的格子中數字的總和。
範例輸入 1
2 7
6 8 7 2 1 4 5
9 3 10 11 12 13 14
範例輸出 1
36
範例輸入 2
4 5
24 7 14 20 30
11 6 4 21 29
2 8 1 35 40
3 9 5 12 15
範例輸出 2
132
留言