Canadian Computing Competition: 2005 Stage 2, Day 2, Problem 2
You are to find the length of the shortest path from the top to the bottom of a grid covering specified points along the way.
More precisely, you are given an ~n~ by ~n~ grid, rows ~1 \dots n~ and columns ~1 \dots n~ ~(1 \le n \le 20\,000)~. On each row ~i~, two points ~L(i)~ and ~R(i)~ are given where ~1 \le L(i) \le R(i) \le n~. You are to find the shortest distance from position ~(1, 1)~, to ~(n, n)~ that visits all of the given segments in order. In particular, for each row ~i~, all the points
$$\displaystyle (i, L(i)), (i, L(i) + 1), (i, L(i) + 2), \dots, (i, R(i)) $$
must be visited. Notice that one step is taken when dropping down between consecutive rows. Note that you can only move left, right and down (you cannot move up a level). On finishing the segment on row ~n~, you are to go to position ~(n,n)~, if not already there. The total distance covered is then reported.
The first line of input consists of an integer ~n~, the number of rows/columns on the grid. On each of the next ~n~ lines, there are two integers ~L(i)~ followed by ~R(i)~ (where ~1 \le L(i) \le R(i) \le n~).
The output is one integer, which is the length of the (shortest) path from ~(1, 1)~ to ~(n, n)~ which covers all intervals ~L(i), R(i)~.
6 2 6 3 4 1 3 1 2 3 6 4 5
Explanation for Sample Output
Below is a pictoral representation of the input.
1 2 3 4 5 6 . _________________________________ ________ _________________ _________ _________________________ _________ .
Notice that on the first row, we must traverse ~5~ units to the right and then drop down one level.
On the second row, we must traverse ~3~ units to the left and drop down one level.
On the third row, we must traverse ~2~ units to the left and drop down one level.
On the fourth row, we move ~1~ unit to the right and then drop down one level.
On the fifth row, we move ~4~ units to the right and drop down one level.
On the sixth (and final) row, we move ~2~ units left, then ~2~ units right.
In total, we have moved ~6 + 4 + 3 + 2 + 5 + 4 = 24~ units.