DMOPC '19 Contest 4 P2 - Pleasant Present

View as PDF

Submit solution

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

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 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). slightlyskepticalpotat can tilt the puzzle, allowing the marble to 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, slightlyskepticalpotat 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, 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, 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 Specification

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.

Sample Input

3 1 1 3 3
1 1
2 2

Sample Output


Sample Explanation


There are no comments at the moment.