← 返回题目列表

AtCoder · abc184_c

C. 超级龙马

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有一个无限的二维网格,我们在方格上有一个叫做超级龙马的棋子 (r_1, c_1). (Ryu 表示龙,Ma 表示马。) 一步棋即可到达如下所示的方格之一:

更正式地说,当超级龙马在广场上时 (a, b),可以去广场 (c, d) 至少满足以下条件之一:

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

求该棋子到达所需的最少移动次数 (r_2, c_2) 来自 (r_1, c_1).

约束

  • 输入中的所有值都是整数。
  • 1 \le r_1, c_1, r_2, c_2 \le 10^9

输入

输入由标准输入按以下格式给出:

r_1 c_1
r_2 c_2

输出

打印超级龙马达到目标所需的最少步数 (r_2, c_2) 来自 (r_1, c_1).


示例输入 1

1 1
5 6

示例输出 1

2

我们需要两个动作 - 例如, (1, 1) \rightarrow (5, 5) \rightarrow (5, 6).


示例输入 2

1 1
1 200001

示例输出 2

2

我们需要两个动作 - 例如, (1, 1) \rightarrow (100001, 100001) \rightarrow (1, 200001).


示例输入 3

2 3
998244353 998244853

示例输出 3

3

我们需要三个动作 - 例如, (2, 3) \rightarrow (3, 3) \rightarrow (-247, 253) \rightarrow (998244353, 998244853).


示例输入 4

1 1
1 1

示例输出 4

0