有一個方格棋盤,棋盤的每一個格子裡都標示了一個整數,而且這些整數都是不相同的。現在有一個機器人在此方格棋盤上行動,每一次機器人只會移動到目前所在位置的上下左右四個相鄰格子中的一格。機器人的起點是數字最小的格子,每次移動會在可以走的位置中挑選數字最小的格子,但是機器人永遠都不會走到他曾經走過的格子,當然他也不會走到範圍之外。當無路可走的時候,機器人就會停下來。輸入方格棋盤中每個格子的數字,請模擬機器人走過的路徑,並輸出機器人走過的格子的數字總和。
以下是一個例子,輸入的 $4\times5$ 的方格內的數字如圖中所標示。在本例子中,機器人的起點會是 1
,所走的路徑是 1
→4
→6
→7
→13
→20
→21
→29
→30
。走到 30
的時候已經無路可走,所以機器人就停止了,而經過的數字總和是 131
。
輸入的第一行是兩個不超過 $100$ 的正整數 $m$ 與 $n$,代表是一個 $m\times n$ 的方格棋盤,接下來有 $m$ 行,每行 $n$ 個數字,分別是方格棋盤由上而下,由左而右的數字。方格內的數字皆為不超過 $100,000$ 的非負整數,同一行數字之間以空白間隔。
輸出機器人走過的格子中數字的總和。
APCS 考古
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 2~6 | $m=1,1\le n\le 100$ | 30 |
3 | 0~13 | 無額外限制 | 70 |