Knight Hop

Interview

Time limit2sMemory limit512 MB

Summary

On an 8 by 8 board, find the fewest knight moves from a start square to a target square.

Level: Medium4 of 10
Topics: BFS, Graph, Shortest path, Implementation
Solved: No attempts yet

Problem

An $8 \times 8$ chessboard is given. Each square is identified by an ordered pair of integers, where each coordinate ranges from $1$ to $8$ . For example, in the diagram below piece A is at position $(2, 2)$ and piece B is at position $(4, 3)$ .

A knight moves in an "L" pattern: it can leap over other pieces to one of up to eight squares. In the diagram below, K marks the knight's current square and the numbers $1$ through $8$ mark the squares it may move to.

Given the knight's starting square and a target square, compute the minimum number of moves needed to move the knight from the start to the target. The knight may never leave the board.

Input

Four integers, each between $1$ and $8$ . The first two give the knight's starting position; the last two give the target position.

Output

Output the minimum number of moves (a non-negative integer) required to move the knight from the start to the target. The knight must not leave the board at any point during the sequence of moves.

Examples2

Example 1
Input
```
2 1
3 3
```
Expected output
```
1
```
Example 2
Input
```
4 2
7 5
```
Expected output
```
2
```