e112. P-7-3. 機器人走棋盤 (APCS 201906) - 花中程式設計挑戰系統

Content

有一個方格棋盤的每一個格子裡都標示了一個不同的整數，有一個機器人在此方格棋盤上行動，每一次只會移動到目前位置的上下左右四個相鄰格子其中之一。起點是數字最小的格子，每次移動則在可以移動位置中挑選數字最小的格子，但是走過的格子就不會再走，當無路可走的時候，機器人就會停下來。輸入方格棋盤中每個格子的數字，請模擬機器人走過的路徑，並輸出機器人走過的格子的數字總和。

以下是一個例子，輸入的 4 x 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

Time limit: 1 秒

Input

輸入的第一行是兩個不超過 100 的正整數 m 與 n，代表是一個 m x n 的方格棋盤，接下來有 m 行，每行 n 個數字，分別是方格棋盤由上而下，由左而右的數字。方格內的數字皆為不超過 1e5 的非負整數，同一行數字之間以空白間隔。

Output

機器人走過的格子中數字的總和。

Sample Input

範例一：
2 7
6 8 7 2 1 4 5
9 3 10 11 12 13 14

範例二：
4 5
24 7 14 20 30
11 6 4 21 29
2 8 1 35 40
3 9 5 12 15

Sample Output

範例一：
36

範例二：
132

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

Hint ：

範例一說明：機器人走的路線是(1,2,7,8,3,9,6)。

範例二說明：此為題目敘述中的範例。

Tags:

BFS

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」