A jump of a knight on an N x N chess board consists of two horizontal steps and one vertical step, or one horizontal step and two vertical steps. For example, consider a knight on position K=(3,2) in the following 5 x 5 board.

                       1   2   3   4   5   
                  1  |   |   |   | X | P |   
                  2  |   |   |   | X |   |   
                  3  |   | K |   | X |   |   
                  4  |   |   |   | X |   |   
                  5  |   |   |   |   |   |   

This knight can jump to positions (1,1), (1,3), (2,4), (4,4), (5,3) and (5,1). The knight can move to position P=(1,5) by jumping first to (5,3), then to (3,4) and then to P. This is the least number of jumps to get from K to P.

The board may contain forbidden positions, indicated by X in the above board. The knight may not land on a forbidden position. In the above situation, the only allowed way to get from K to P with 3 jumps is via (1,1) and (2,3).

Write a program that, given a board size N, an initial position K of the knight, a target position P and a list of forbidden positions, computes the least number of jumps to get from K to P while not landing on any forbidden positions. The board size N in the test data and the number of forbidden positions both range from 5 to 50.

Output the value -1 if there is no way to get from K to P without landing on any forbidden positions.


The input contains

  • the board size N on the first line,
  • the initial position K of the knight on the second line,
  • the target position P on the third line,
  • the number T of forbidden positions on the fourth line, followed by T lines each containing a forbidden position.

The input data corresponding to the chess board shown in the example above is as follows.

3 2
1 5
1 4
2 4
3 4
4 4

On the first line is the number 5 of rows and columns. Next is the initial position K, which is (3,2). The target position P is given on the third line. Next, the number of forbidden positions, 4 in this example, is given. The list of forbidden positions follows, one per line.


The output should contain an integer which indicates the number of jumps in the shortest move from K to P. Output -1 if there is no solution.

For the above example, the output will be:


Submitting .cpp to 'knightmoves'

You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0