Santa was not benevolent with his presents this year. ~N~ by ~N~ grid where the top left corner is represented by ~(1,1)~ and the bottom-right corner is represented by ~(N,N)~. A marble starts at ~(r_s,c_s)~ and must make its way to ~(r_e,c_e)~. can tilt the puzzle, allowing the marble move to an adjacent cell, using ~1~ second of time. However, in this puzzle, all but ~2~ cells are blocked by magnets which repel the marble. This means that there may not be an empty direct path from ~(r_s,c_s)~ to ~(r_e,c_e)~. To circumvent this, can slide a magnet into another adjacent empty cell using ~1~ second of time, (effectively swapping the positions of the empty cell with the magnet cell). It is guaranteed that ~(r_s,c_s)~ 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, ~N~, ~r_s~, ~c_s~, ~r_e~, ~c_e~, 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.
~2 \le N \le 15~
~1 \le r_i,c_i \le N~
~(r_s,c_s)~ is originally empty and is one of the two inputted empty cells.
3 1 1 3 3 1 1 2 2