C - Super Ryuma Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

無限に広がる 2 次元グリッドがあり、マス (r_1, c_1) に駒「超竜馬」が置かれています。
この駒は、 1 手で次のような動きができます。

より正確には、超竜馬がマス (a, b) にあるとき、以下のいずれかの条件を満たすマス (c, d) に動かすことができます。

  • a + b = c + d
  • a - b = c - d
  • |a - c| + |b - d| \le 3

超竜馬を (r_1, c_1) から (r_2, c_2) に動かすのに必要な最小手数を求めてください。

制約

  • 入力は全て整数
  • 1 \le r_1, c_1, r_2, c_2 \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

r_1 c_1
r_2 c_2

出力

超竜馬を (r_1, c_1) から (r_2, c_2) に動かすのに必要な最小手数を出力せよ。

入力例 1

1 1
5 6

出力例 1

2

例えば、 (1, 1) \rightarrow (5, 5) \rightarrow (5, 6) と動かすと 2 手になります。

入力例 2

1 1
1 200001

出力例 2

2

例えば、 (1, 1) \rightarrow (100001, 100001) \rightarrow (1, 200001) と動かすと 2 手になります。

入力例 3

2 3
998244353 998244853

出力例 3

3

例えば、 (2, 3) \rightarrow (3, 3) \rightarrow (-247, 253) \rightarrow (998244353, 998244853) と動かすと 3 手になります。

入力例 4

1 1
1 1

出力例 4

0

Score : 300 points

Problem Statement

There is an infinite two-dimensional grid, and we have a piece called Super Ryuma at square (r_1, c_1). (Ryu means dragon and Ma means horse.) In one move, the piece can go to one of the squares shown below:

More formally, when Super Ryuma is at square (a, b), it can go to square (c, d) such that at least one of the following holds:

  • a + b = c + d
  • a - b = c - d
  • |a - c| + |b - d| \le 3

Find the minimum number of moves needed for the piece to reach (r_2, c_2) from (r_1, c_1).

Constraints

  • All values in input are integers.
  • 1 \le r_1, c_1, r_2, c_2 \le 10^9

Input

Input is given from Standard Input in the following format:

r_1 c_1
r_2 c_2

Output

Print the minimum number of moves needed for Super Ryuma to reach (r_2, c_2) from (r_1, c_1).

Sample Input 1

1 1
5 6

Sample Output 1

2

We need two moves - for example, (1, 1) \rightarrow (5, 5) \rightarrow (5, 6).

Sample Input 2

1 1
1 200001

Sample Output 2

2

We need two moves - for example, (1, 1) \rightarrow (100001, 100001) \rightarrow (1, 200001).

Sample Input 3

2 3
998244353 998244853

Sample Output 3

3

We need three moves - for example, (2, 3) \rightarrow (3, 3) \rightarrow (-247, 253) \rightarrow (998244353, 998244853).

Sample Input 4

1 1
1 1

Sample Output 4

0