機器人的路徑 (APCS 2019-06 中級)

地面被劃分成一個 \(n\) 列、\(m\) 行的方格地圖。第 \(r\) 列、第 \(c\) 行的格子記為 \((r,c)\)，其中寫著整數 \(a_{r,c}\)。地圖中的所有數值都不相同。

一台機器人會按照以下規則移動：

1. 在整張地圖中找出數值最小的格子，將它作為起點。起點立刻標記為「已走過」，它的數值也要計入總和。
2. 假設機器人目前位於 \((r,c)\)。它只會查看與 \((r,c)\) 共用一條邊的格子，也就是上、下、左、右四個方向；斜對角不算相鄰。
3. 在這些相鄰格子中，先排除超出地圖邊界或已經走過的格子。
4. 如果還有候選格，機器人移動到其中數值最小的一格，將新格子標記為已走過，並把它的數值加入總和，接著回到步驟 2。
5. 如果沒有任何候選格，機器人立刻停止。

由於所有格子的數值互不相同，所以起點與每一步要走的格子都是唯一的。請計算機器人整條路徑上所有數值的總和。

請注意：機器人停止時，地圖上可能仍有沒走過的格子；它不會跳到不相鄰的格子重新出發。

下圖展示第二筆範例。格子左上角的小圓圈是走訪順序；綠框是起點、藍框是途中經過的格子、紅框是終點，灰色虛線框則表示沒有走到的格子。

機器人的路徑依序為

\[1\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow8\rightarrow14\rightarrow13\rightarrow12.\]

到達數值 \(12\) 的格子後，它的上方 \(13\) 與左方 \(4\) 都已走過，右方與下方又超出邊界，因此停止。數值 \(9,7,6\) 雖然尚未走過，也不會被加入總和。

輸入格式

第一行包含兩個整數 \(n\)、\(m\)，分別表示地圖的列數與行數。

接下來 \(n\) 行，每行包含 \(m\) 個整數。第 \(r\) 行的第 \(c\) 個整數為 \(a_{r,c}\)。

限制

• \(1\le n,m\le100\)
• \(0\le a_{r,c}<1000000\)
• 所有 \(a_{r,c}\) 互不相同。
• 所有輸入都是整數。

輸出格式

輸出一個整數，表示機器人走過的所有格子數值總和。起點與終點都要計入。

答案可能超過 \(32\) 位元有號整數的範圍。

評分說明

兩筆範例會由評測系統執行，但不計分。另有恰好 \(20\) 個計分子題組，每組 \(5\) 分：

• 第 \(1\)～\(4\) 組（共 \(20\) 分）：\(n=1\)。
• 第 \(5\)～\(8\) 組（再增加 \(20\) 分）：\(1\le n,m\le20\)。連同前四組，共有 \(40\) 分符合此限制。
• 第 \(9\)～\(20\) 組（其餘 \(60\) 分）：沒有額外限制。

範例輸入 1

1 7
1 2 3 4 5 6 7

範例輸出 1

28

範例解釋 1

起點是數值 \(1\) 的格子。機器人只能一路向右走，依序走過 \(1,2,3,4,5,6,7\)，總和為 \(28\)。

範例輸入 2

3 4
9 1 8 14
7 2 5 13
6 3 4 12

範例輸出 2

62

範例解釋 2

移動順序如上圖。路徑總和為

\[1+2+3+4+5+8+14+13+12=62.\]

題目來源

APCS 2019 年 6 月實作題第 2 題；規則參考 ZeroJudge e287「機器人的路徑」 與王一哲的 HackMD 題解，題目敘述與輔助圖由 AACPOJ 重新整理。