Under construction

Still being built. Things may change

Minimum Queen Moves

Interview

Time limit2sMemory limit512 MB

Summary
Given a queen's start and target square on an 8x8 board, print the minimum number of queen moves needed.
Level

Medium4 of 10

Topics
Math, Implementation, Geometry
Solved
No attempts yet

Problem

A chess queen moves any number of squares at once along its row, along its column, or along one of the two diagonals. The figure below shows the squares a queen reaches in a single move.

8x8 board with the squares a queen can reach in one move

The chess grandmaster Kary Gasparov invented a new kind of problem. A single queen stands on an 8 x 8 board with 64 squares and no other piece on it. Given a target square, what is the smallest number of moves the queen needs to get there?

Kary solved some of these cases himself but got stuck on the rest, so write a program that answers them.

Input

The input holds several test cases. Each test case is one line with four integers X1X_1, Y1Y_1, X2X_2, Y2Y_2 separated by spaces (1≤X1,Y1,X2,Y2≤81 \le X_1, Y_1, X_2, Y_2 \le 8). The queen starts on the square with coordinates (X1,Y1)(X_1, Y_1), and the target is the square with coordinates (X2,Y2)(X_2, Y_2).

Columns are numbered 1 to 8 from left to right and rows are numbered 1 to 8 from top to bottom. The square in row XX and column YY has coordinates (X,Y)(X, Y).

The last line of the input holds four zeros. Do not process that line.

Output

For each test case print one line with one integer, the smallest number of moves the queen needs to reach its target square.

Examples4

  1. Example 1

    Input
    4 4 6 2
3 5 3 5
5 5 4 3
0 0 0 0
    Expected output
    1
0
2

  2. Example 2

    Input
    1 1 1 8
8 1 1 1
4 7 4 2
6 3 6 3
0 0 0 0
    Expected output
    1
1
1
0

  3. Example 3

    Input
    1 1 8 8
8 8 1 1
1 8 8 1
8 1 1 8
0 0 0 0
    Expected output
    1
1
1
1

  4. Example 4

    Input
    1 1 2 3
2 3 1 1
1 1 3 2
8 8 7 6
0 0 0 0
    Expected output
    2
2
2
2