CCO '12 P4 - Editor Distance

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2012 Day 2, Problem 1:

You are using an editor to type in a program that you hope solves another problem on this contest. Instead of thinking about solving this problem, you look at your editor and start to think of how to edit your program more quickly.

Your editor has the following characteristics:

  • you can move your cursor using the direction keys: up (\uparrow), down (\downarrow) , left (\leftarrow) or right (\rightarrow)
  • pressing \rightarrow will move the cursor one character to the right; if the cursor is on the rightmost character of a line, the cursor will move to the first character of the next line below the current line; (the cursor will not move if it is in the bottom-right position)
  • pressing \leftarrow will move the cursor one character to the left; if the cursor is on the leftmost character of a line, the cursor will move to the last character of the previous line above the current line; (the cursor will not move if it is in the top-left position)
  • pressing \uparrow will move the cursor to the character immediately above it; if there is no character immediately above the cursor, it will move to the last character of the previous line above the current line; (the cursor will not move if it is on the first line)
  • pressing \downarrow will move the cursor to the character immediately below it; if there is no character immediately below the cursor, it will move to the last character of the next line below the current line; (the cursor will not move if it is on the last line)

You would like to find the least number of key presses that will cause you to move between positions in your editor in a given program which you are editing.

Input Specification

The first line of input is N, the number of lines of your program (1 \leq N \leq 100000). The next N lines contain the number of characters on each line: you can assume there is at least one character per line, and at most 80 characters per line. The next line contains two integers R_S\,C_S, indicating the starting row and column of the cursor (1 \leq R_S \leq N, 1 \leq C_S, and C_S is at most the number of characters in row R_S). The last line contains two integers R_F\,C_F, indicating the finishing row and column of the cursor (1 \leq R_F \leq N, 1 \leq C_F, and C_F is at most the number of characters in row R_F).

Output Specification

Output the minimum number of key presses that are required to move the cursor from row R_S and column C_S to row R_F and column C_F.

Sample Input

4
40
10
4
80
4 78
1 35

Output for Sample Input

10

Comments

There are no comments at the moment.