torus711 のアレ

主に競技プログラミングの問題について書きます

AtCoder Beginner Contest 184, C : Super Ryuma

問題概要

 グリッド状の無限に広い盤面の位置 $( 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;