Description

In various board games, the movement of pieces is always fixed. For example, in Chinese chess, the horse moves in an "日" shape. A primary school student thought it would be more interesting if the horse had two movement options, so he decided that the horse could move in the "日" shape as well as the "田" shape, similar to the elephant's movement.

His deskmate, who enjoys playing Go, found this idea intriguing and wanted to try it out. On a 100×100 Go board, they randomly selected two points, A and B. A black stone is placed at point A, and a white stone at point B, representing two horses. The stones can move either in the "日" shape or the "田" shape. The two players take turns moving the black and white horses, respectively. The one who reaches the top-left corner with coordinates (1, 1) in the fewest steps wins.

Now, the deskmate asks for your help. Given the coordinates of points A and B, you need to determine the minimum number of steps required for each position to reach (1, 1).

Input Format

The coordinates of points A and B.

Output Format

The minimum number of steps.

Example Input

12 16
18 10

Example Output

8
9

Explanation

For the given input, the black horse at (12, 16) reaches (1, 1) in 8 steps, while the white horse at (18, 10) takes 9 steps.

Constraints

• The coordinates of A and B are integers within the range [1, 100].
• The output should consist of two integers, representing the minimum steps for A and B, respectively.

Approach

1. Breadth-First Search (BFS): Since the board is 100×100, BFS is suitable for finding the shortest path from any point to (1, 1).
2. Movement Rules: The horse can move in 12 possible directions:
   • 8 "日" moves: (±1, ±2), (±2, ±1).
   • 4 "田" moves: (±2, ±2).
3. Queue Initialization: Start BFS from (1, 1) and propagate outward to compute the minimum steps for all reachable positions.
4. Visited Tracking: Use a distance matrix to record the minimum steps required to reach each position.

Solution Code

from collections import deque

def compute_min_steps():
    # Define all possible moves (日 and 田)
    moves = [
        (1, 2), (2, 1), (-1, 2), (-2, 1),
        (1, -2), (2, -1), (-1, -2), (-2, -1),
        (2, 2), (2, -2), (-2, 2), (-2, -2)
    ]
    
    # Initialize distance matrix with -1 (unvisited)
    size = 100
    dist = [[-1 for _ in range(size + 1)] for _ in range(size + 1)]
    
    q = deque()
    # Start from (1, 1)
    q.append((1, 1))
    dist[1][1] = 0
    
    while q:
        x, y = q.popleft()
        for dx, dy in moves:
            nx = x + dx
            ny = y + dy
            if 1 <= nx <= size and 1 <= ny <= size and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    
    return dist

# Precompute distances for all positions
dist = compute_min_steps()

# Read input
Ax, Ay = map(int, input().split())
Bx, By = map(int, input().split())

# Output the results
print(dist[Ax][Ay])
print(dist[Bx][By])

Explanation

1. Movement Setup: The moves list includes all 12 possible directions the horse can move (8 "日" moves and 4 "田" moves).
2. BFS Initialization: The BFS starts from (1, 1), marking its distance as 0.
3. Distance Propagation: For each position, the algorithm checks all 12 moves, updating the distance for valid, unvisited positions.
4. Result Query: After precomputing distances for all positions, the solution reads the input coordinates and outputs their precomputed distances.

This approach efficiently computes the shortest path for any starting position on the 100×100 grid using BFS, ensuring optimal performance and correctness.

12 16
18 10

8
9