You are using a very simple text editor to create a document. You have typed in several lines, with the flashing cursor advancing as you type, but then you see a mistake on a previous line. Unfortunately, the mouse doesn’t work! You will have to press arrow keys to move the cursor back to the position where you can fix the mistake. Of course, you want to get to this position as quickly as possible.
This simple editor uses a monospace font, so each character is exactly the same width. The cursor can be at the beginning of the line (before the first character), end of the line (after the last character), or at a horizontal position between two characters on a given line. The following keys can be pressed to move the cursor (each keypress is independent of any preceding keypress):
Given the line lengths of a text file that was loaded in this simple editor, along with the current cursor position and a different, desired cursor position (e.g., to fix a mistake), you are to determine the minimum number of keypresses, using arrow keys only, required to move the cursor to the desired position.
The first input line contains a positive integer, n, indicating the number of editor navigation scenarios to process. Each scenario will occupy exactly 4 input lines. The first line of each scenario contains an integer f (1 ≤ f ≤ 120), indicating the number of lines of text in the file that is loaded in the editor. The next input line contains f integers, s1 to sf, where each value si (0 ≤ si ≤ 80) indicates the number of characters on line i of the file; the values will be separated by exactly one space. A value si = 0 means that there are no characters on line i. The newline character (common character indicating end of a line) does not count as a character on the line.
The third input line of each scenario will contain two integers (separated by a space) providing the current cursor position in the file: rc (1 ≤ rc ≤ f) and cc (0 ≤ cc ≤ 80), where rc represents the line of the file, counting from 1 (as with i), and cc represents the horizontal position of the cursor on that line, 0 for the beginning (before the first character). It is guaranteed that the cursor position is valid, so if, for instance, rc = 17 and s17 = 56, then 0 ≤ cc ≤ 56; the maximum value of cc is the end of the line. The fourth input line of each scenario is similar to the third and indicates the desired cursor position to begin fixing the mistake, i.e., this line consists of two integers separated by a space, rm (1 ≤ rm ≤ f) and cm (0 ≤ cm ≤ 80). The constraints on the values for rc and cc also apply to rm and cm.
For each scenario in the input, output a single integer on a line by itself indicating the minimum number of keypresses needed to move the cursor from its current position (rc, cc) to the desired position (rm, cm) for fixing the mistake.
39 20 57 54 14 38 31
15 30 20
For Case #1, one possible sequence for the minimum number of keypresses to move the cursor from its current position to the desired position is: Up, Up, Right, Up, Left, Up, Left 15 times.