[AtCoder] ABC 184 C – Super Ryuma

2020年11月23日2020年12月12日

問題

方針

\( (r_1, c_1)\) から \(( r_2, c_2) \) への移動は、\( x = |r_2 – r_1| \)、\( y = |c_2 – c_1| \) として、\( (0, 0)\) から \( (x, y) \) への移動を考えることと同じです。

\( 1 \) 回の移動の移動で \( (0, 0) \)行くことができるマスは、整数 \( a \) を用いて、

\[ (a, a), (a, -a)\]

と

\[ ( i,  j) \ (|i| + |j | \leq 3)\]

と表現できます。\( 2 \) 回の移動の移動で \( (0, 0) \) から行くことができるマスは、\( 1 \) 回の移動を考慮し、整数 \( b \) を用いて、

\[ (a + b, a – b) , (i + b, j + b), (i + b, j – b) \]

と

\[ (k, l) \ (|k| + |l| \leq 6)\]

と表現できます。ここで、変数 \( a, b \) についての方程式を考えます。

\begin{eqnarray}
a + b &=& x\\
a – b &=& y
\end{eqnarray}

この方程式の解は、

\[ a = \dfrac{x + y}{2} \wedge b = \dfrac{x – y}{2}\]

となります。\( (x + y) \bmod 2 = 0 \) であるとき、\( (x – y) \bmod 2 = 0 \) です。なので、\( (x + y) \bmod 2 = 0 \) であるとき \( 2 \) 回の移動の移動で \( (0, 0) \) から \( (x, y)\) へ移動することができます。このことから、\( (x + y) \bmod 2 = 1 \) のときは、\( (0, 0) \) から \( (1, 0) \) へと移動することで、少なくとも \( 3 \) 回の移動で、 \( (0, 0) \) から \( (x, y)\) へ移動することができます。

コード

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

int main() {
    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    ll x = abs(r1 - r2);
    ll y = abs(c1 - c2);
    int ans = 3;
    if (x == 0 && y == 0) {
        ans = 0;
    } else if (x == y || x + y <= 3) {
        ans = 1;
    } else if ((x + y) % 2 == 0 || x + y <= 6) {
        ans = 2;
    } else {
        for (int i = -3; i <= 3; i++) {
            for (int j = -3; j <= 3; j++) {
                if (abs(i) + abs(j) <= 3) {
                    if (abs(x - i) == abs(y - j)) {
                        ans = 2;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}