Skills101
← All coding problems

Knight Minimum Moves

mediumGraphs II+20 XPTime limit 3s

A chess knight stands on square (a, b) of an n × n board (rows and columns numbered 1 … n). A knight moves in an "L": two squares in one direction and one square at a right angle — up to 8 possible moves, and it may never leave the board. What is the minimum number of moves to reach square (x, y)?

Input: one line n a b x y.

Output: the minimum number of moves, or -1 if the target cannot be reached.

Constraints: 1 ≤ n ≤ 300, 1 ≤ a, b, x, y ≤ n.

Think about it: squares are nodes and knight moves are edges, all of cost 1 — so BFS from the start gives the answer. Mark a square visited when you push it, and stop as soon as you reach the target. On tiny boards (n = 2 or 3) some squares are unreachable.

Sample input 1

8 1 1 8 8

Sample output 1

6

Sample input 2

3 1 1 2 2

Sample output 2

-1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.