DMOPC '19 Contest 4 P2 - Pleasant Present

View as PDF

Submit solution


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

Author:
Problem type

Santa was not benevolent with his presents this year. Anthony 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 (rs,cs) and must make its way to (re,ce). Anthony 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 (rs,cs) to (re,ce). To circumvent this, Anthony 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 (rs,cs) is originally empty. Because he isn't very dexterous, Anthony can only do one of the two moves (tilting the puzzle or moving a magnet) at any given time.

Anthony 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, rs, cs, re, ce, 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

2N15

1ri,ciN

(rs,cs) is originally empty and is one of the two inputted empty cells.

Sample Input

Copy
3 1 1 3 3
1 1
2 2

Sample Output

Copy
11

Sample Explanation


Comments

There are no comments at the moment.