Minimum Knight Moves

On a standard 8x8 chessboard, a knight moves in an L-shape: two cells in one direction and one cell in a perpendicular direction. Mathematically, its moves can be described as \( (\pm1, \pm2) \) or \( (\pm2, \pm1) \). Given a starting position \( (x_0, y_0) \) and a target position \( (x_1, y_1) \), your task is to compute the minimum number of moves required for the knight to reach the target position. If the starting and target positions are the same, the answer is 0.

The problem can be solved efficiently using a Breadth-First Search (BFS) algorithm on the chessboard, ensuring that you calculate the shortest path. Note that the chessboard coordinates range from 1 to 8 for both rows and columns.

inputFormat

The input is provided via stdin and consists of multiple lines. Each line contains four space-separated integers \(x_0\), \(y_0\), \(x_1\), and \(y_1\) representing the starting and target positions on the chessboard, where \(1 \leq x_0, y_0, x_1, y_1 \leq 8\). The input terminates with a line containing "0 0 0 0", which should not be processed.

outputFormat

For each test case (excluding the termination line), output the minimum number of moves required for the knight to reach the target position. Each output should be written to stdout on a separate line.

1 1 8 8
0 0 0 0

6