問題概要

以下の動きのできる駒がある。駒をマス $(a, b)$ からマス $(c, d)$ へ移動させるのに必要な手数の最小値を求めよ。

制約

$1 \le a, b, c, d \le 10^{9}$

考えたこと

まず、スタートとゴールの位置関係を平行移動して

$(0, 0)$ から $(c-a, d-b)$ へと移動させる問題

とみなしても変わらない。さらに対称性から

$(0, 0)$ から $(|c-a|, |d-b|)$ へと移動させる問題

とみなしても変わらない。よって、 $p = |c-a|$ 、 $q = |d-b|$ とおいて考えることにする。まず明らかなケースとして、次のことが言える。

$p = q = 0$ のときは、0 回
それ以外で $p = q$ のときは、1 回
それ以外で $p + q \le 3$ のときは、1 回
それ以外の場合は 2 回以上かかる

また下図のように盤面全体を市松模様に塗ることにしたとき、同じ色のマスからマスへは、どんなに遠く離れていても、からなず 2 回以下で行けることに注意しよう。

よって、どんなケースであってもかならず 3 手以内に到達できる。具体的には

同じ色であれば 2 手 (以内)
異なる色であれば、まず最初に 1 回真横に移動して (色を変える)、そこから 2 手 (以内)

というふうにすればよい。よって、明らかなケースを除いて「2 手」か「3 手」かを特定する問題だと言える。

2 手で行ける場合

1 手以内で行ける場合は予め除外した上で、2 手で行ける場合を列挙していこう。

$p + q$ が偶数のとき (スタートと同じ色のマス)
$p + q \le 6$ のとき (1 回の移動で $p+q$ を 3 増やせるので)
$|p-q| \le 3$ のとき (最初に $(p, p)$ まで移動して、そこから 1 手で行ける)

これら以外には行けないことが言える。念のために簡単に証明してみる。 $p + q$ が奇数の場合を考えれば十分。 $p + q$ が奇数のとき、2 回の移動のうちの 1 回は「色を変える移動」をする必要があるが、それが最初の移動であるとしてよい (2 回目の移動で色を変える場合であっても、1 回目と 2 回目を入れ替えても結果は変わらないため)。つまり、2 回の移動のうちの最初の移動において $|p+q| \le 3$ を満たすいずれかのマスに進むものとしてよい。

そのマスから次に行けるマスを列挙すると、

$p + q \le 6$ のとき (1 回の移動で $p+q$ を 3 増やせるので)
$|p-q| \le 3$ のとき (最初に $(p, p)$ まで移動して、そこから 1 手で行ける)

のいずれかに限定される。

まとめ

$p = q = 0$ のとき、0 回
それ以外で $p = q$ または $p + q \le 3$ のとき、1 回
それ以外で以下を満たすとき、2 回
- $p + q$ が偶数のとき
- $p + q \le 6$ のとき
- $|p-q| \le 3$ のとき
それ以外のとき、3 回

計算量は $O(1)$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    auto solve = [&]() -> long long {
        long long p = abs(c - a), q = abs(d - b);
        if (p == 0 && q == 0) return 0;
        if (p == q || p + q <= 3) return 1;
        if ((p + q) % 2 == 0 || p + q <= 6 || abs(p - q) <= 3) return 2;
        return 3; 
    };
    cout << solve() << endl;
}