DMOPC '19 Contest 4 P2 - Pleasant Present

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Santa was not benevolent with his presents this year. slightlyskepticalpotat is an unfortunate little boy who received a puzzle for Christmas. The puzzle is shaped like an by grid where the top left corner is represented by and the bottom-right corner is represented by . A marble starts at and must make its way to . slightlyskepticalpotat can tilt the puzzle, allowing the marble to move to an adjacent cell, using second of time. However, in this puzzle, all but cells are blocked by magnets which repel the marble. This means that there may not be an empty direct path from to . To circumvent this, slightlyskepticalpotat can slide a magnet into another adjacent empty cell using second of time, (effectively swapping the positions of the empty cell with the magnet cell). It is guaranteed that is originally empty. Because he isn't very dexterous, slightlyskepticalpotat can only do one of the two moves (tilting the puzzle or moving a magnet) at any given time.

slightlyskepticalpotat was promised a reward from Santa if he finishes the puzzle. Wanting to get his present as soon as possible and being technologically inept, he hired you to create a program to find the shortest amount of time he will take to complete the puzzle.

Note: adjacent cells must share a common side.

Input Specification

The first line of input will consist of five positive integers, , , , , , representing the size of the grid, the starting row of the marble, the starting column of the marble, the destination row, and the destination column.

The next 2 lines each contain a pair of space-separated positive integers representing the original positions of the empty cells.

Output Specification

Output a single integer, the minimum amount of time required to complete the puzzle.

Constraints

is originally empty and is one of the two inputted empty cells.

Sample Input

3 1 1 3 3
1 1
2 2

Sample Output

11