AtCoder Beginner Contest 184, C : Super Ryuma

問題文

　https://atcoder.jp/contests/abc184/tasks/abc184_c

問題概要

　グリッド状の無限に広い盤面の位置 $( r_1, c_1 )$ に駒が置かれている．この駒が位置 $( a, b )$ にあるとき，次の条件のいずれかを満たす位置 $( c, d )$ へ一手で動かすことができる．

• $a + b = c + d$
• $a - b = c - d$
• $| a - c | + | b - d | \leq 3$

ざっくり言うと，斜め方向への任意長の移動とマンハッタン距離 $3$ 以内の移動が行える．
　位置 $( r_2, c_2 )$ へ移動させるときの最短手数はいくらか？

制約

• $1 \leq r_1, c_1, r_2, c_2 \leq 10^9$

解法

　すぐに確かめられることがいくつかあります．入力の 2 地点が問題文の条件を満たすとき，$1$ 手で行けます．また，2 地点が同一のとき，動かす必要が無いので $0$ 手です．また，盤面が無限に広いので，位置のパリティ（座標値の和の $\bmod 2$）が等しい位置へは $2$ 手で行けます．最初に横にズラすとパリティを変えられるので，最悪でも $3$ 手しかかかりません．一旦ここまでをまとめると，

• $r_1 = r_2$ かつ $c_1 = c_2$ のとき : $0$
• $a + b = c + d$ または $a - b = c - d$ または $| a - c | + | b - d | \leq 3$ のとき : $1$
• $( r_1 + c_1 ) \bmod 2 = ( r_2 + c_2 ) \bmod 2$ のとき : $2$
• それ以外のケース : $2$ or $3$ ?

です．
　残ってるケースは，「$1$ 手では行けない状況で，$2$ 手で足りるか？」という判定です．このあたりはちょっとよく分からないので，わたしは経由点を全パターン試しました．移動（相対的にどこに動かすか）の順序は入れ替えてもよいので，$1$ 手目と $2$ 手目の着地位置を全通り（それぞれ始点近辺と終点近辺としてよい）は試すことができます．

コード

int solve( const int a, const int b, const int c, const int d )
{
	if ( a == c && b == d )
	{
		return 0;
	}
	if ( ( a + b == c + d ) ||
			( a - b == c - d ) ||
			( abs( a - c ) + abs( b - d ) <= 3 ) )
	{
		return 1;
	}
	if ( ( a + b ) % 2 == ( c + d ) % 2 )
	{
		return 2;
	}
	return 4;
}

int main()
{
	IN( int, A, B, C, D );

	if ( solve( A, B, C, D ) <= 2 )
	{
		cout << solve( A, B, C, D ) << endl;
		return 0;
	}

	int res = 3;
	REP( a, A - 3, A + 4 )
	{
		REP( b, B - 3, B + 4 )
		{
			REP( c, C - 3, C + 4 )
			{
				REP( d, D - 3, D + 4 )
				{
					chmin( res, solve( A, B, a, b ) + solve( a, b, c, d ) + solve( c, d, C, D ) );
				}
			}
		}
	}
	cout << res << endl;

	return 0;