Santa was not benevolent with his presents this year. 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 . can tilt the puzzle, allowing the marble 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, 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, can only do one of the two moves (tilting the puzzle or moving a magnet) at any given time.is an unfortunate little boy who received a puzzle for Christmas. The puzzle is shaped like a
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.
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 a single integer, the minimum amount of time required to complete the puzzle.
is originally empty and is one of the two inputed empty cells.
3 1 1 3 3 1 1 2 2