マス \((a, b)\) からマス \((c, d)\) に移動できる \(3\) つの条件

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

のそれぞれによる移動を移動 A, B, C と呼ぶことにします。

まずは、より遠くに移動することができる移動 A と移動 B について考えましょう。
移動 A と移動 B を 1 回ずつ使うと、パリティの等しい (下図において色の同じ) 任意のマスに 2 手で移動することができます。
(これは、グリッド全体を \(45\) 度回転させると分かりやすいです。)

したがって、移動 C も合わせると、任意のマスに \(3\) 手で移動できることが分かります。

答えが \(3\) 以下になることがわかったので、 \(0\) 手、 \(1\) 手、 \(2\) 手でそれぞれ移動できるかを判定できれば、この問題を解くことができます。
\(0\) 手は同じマスかどうか、\(1\) 手は上の \(3\) つの条件を調べれば良いです。
\(2\) 手については、いくつかのパターンに分けられます。

• 移動 A + 移動 B :
  
  • パリティが等しい (上図において色が同じ) かどうか
    
  • \((a + b + c + d) \bmod 2 = 0\)
• 移動 C + 移動 C :
  
  • マンハッタン距離が \(6\) 以下かどうか
  • \(|a - c| + |b - d| \le 6\)
• 移動 A + 移動 C :
  
  • 下図参照
  • \(|(a + b) - (c + d)| \le 3\)
• 移動 B + 移動 C :
  • 下図参照
  • \(|(a - b) - (c - d)| \le 3\)

これらを実装すると、 AC が得られます。

実装例 (Python)

r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())
r = r2 - r1
c = c2 - c1

if (r, c) == (0, 0):
    ans = 0
elif r == c or r == -c: 
    ans = 1
elif abs(r) + abs(c) <= 3:
    ans = 1
elif (r ^ c ^ 1) & 1:
    ans = 2
elif abs(r) + abs(c) <= 6:
    ans = 2
elif abs(r + c) <= 3 or abs(r - c) <= 3:
    ans = 2
else:
    ans = 3

print(ans)

実装例 (C++)

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

int main(){
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    int r = r2 - r1, c = c2 - c1;
    int ans = 3;
    if(!r && !c) ans = 0;
    else if(r == c || r == -c || abs(r) + abs(c) <= 3) ans = 1;
    else if((r ^ c ^ 1) & 1 || abs(r + c) <= 3 || abs(r - c) <= 3 || abs(r) + abs(c) <= 6) ans = 2;
    cout << ans << endl;
}