Robot's Path (APCS 2019-06 Intermediate)

The ground is divided into a grid with \(n\) rows and \(m\) columns. The cell in row \(r\) and column \(c\) is denoted by \((r,c)\) and contains an integer \(a_{r,c}\). All values in the grid are distinct.

A robot moves according to the following rules:

1. Find the cell with the smallest value in the entire grid and use it as the starting cell. Immediately mark it as visited and include its value in the sum.
2. Suppose the robot is currently at \((r,c)\). It considers only cells that share an edge with \((r,c)\): up, down, left, and right. Diagonal cells are not adjacent.
3. Discard candidates that are outside the grid or have already been visited.
4. If at least one candidate remains, move to the candidate with the smallest value, mark it as visited, add its value to the sum, and repeat from step 2.
5. If no candidate remains, stop immediately.

Since all grid values are distinct, both the starting cell and every move are uniquely determined. Compute the sum of the values along the robot's entire path.

The robot may stop while some cells are still unvisited. It never jumps to a non-adjacent cell to start again.

The following diagram shows sample 2. The small circle in the upper-left corner of a cell is its visit number. The green outline marks the start, blue outlines mark intermediate visited cells, the red outline marks the final cell, and dashed gray cells are never visited.

The path is

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

At value \(12\), the cells above (\(13\)) and to the left (\(4\)) are already visited, while the cells to the right and below are outside the grid. The robot therefore stops. Values \(9,7,6\) remain unvisited and are not added.

Input

The first line contains two integers \(n\) and \(m\), the number of rows and columns.

Each of the next \(n\) lines contains \(m\) integers. The \(c\)-th integer on the \(r\)-th line is \(a_{r,c}\).

Constraints

• \(1\le n,m\le100\)
• \(0\le a_{r,c}<1000000\)
• All \(a_{r,c}\) are distinct.
• All input values are integers.

Output

Print one integer: the sum of all values in cells visited by the robot. Include both the starting and final cells.

The answer may exceed the range of a signed 32-bit integer.

Scoring

The two samples are judged but worth zero points. There are exactly \(20\) scored groups worth \(5\) points each:

• Groups \(1\)–\(4\) (\(20\) points): \(n=1\).
• Groups \(5\)–\(8\) (an additional \(20\) points): \(1\le n,m\le20\). Together with the first four groups, \(40\) points satisfy this limit.
• Groups \(9\)–\(20\) (the remaining \(60\) points): no additional constraints.

Sample Input 1

1 7
1 2 3 4 5 6 7

Sample Output 1

28

Sample Explanation 1

The robot starts at value \(1\) and can only move right, visiting \(1,2,3,4,5,6,7\). Their sum is \(28\).

Sample Input 2

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

Sample Output 2

62

Sample Explanation 2

The visit order is shown in the diagram. The path sum is

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

Source

APCS June 2019, implementation problem 2. The rules are based on ZeroJudge e287, “Robot's Path” and Wang Yizhe's HackMD explanation; AACPOJ rewrote the statement and created the explanatory diagram.