torus711 のアレ

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

TopCoder SRM 628, Division 2, Level 1 : BishopMove

問題概要

 8 \times 8 のチェス盤上の位置 ( r_1, c_1 ) にビショップが置かれている。このビショップを位置 ( r_2, c_2 ) に移動させるために必要な手数の最小値を求めよ。到達不可能な場合は -1 で示せ。
 ※ビショップの動きは将棋の角と同じ。斜め方向に任意長移動できる。

解法

 まず、Wikipedia などでチェス盤の画像を眺めてみると、移動が可能(マスの色が同じ)であるとすれば、盤上のどの位置へも高々 2 手で移動できることに気が付きます。以降は、これを踏まえて最小手数の計算を簡潔に表現する方法を考えます。
 初期位置と目的地の間の、行と列の座標の差(の絶対値)をそれぞれ d_1, d_2 とします。このとき、「駒が目的地に到達した状態」は d_1 = d_2 = 0 であるような場合に対応します。また、駒を動かす操作はある定数 k を用いて  \left( \begin{matrix} d_1 \\ d_2 \end{matrix} \right) + \left( \begin{matrix} \pm k \\ \pm k \end{matrix} \right) と表せます。このことから分かるように、d_1 \neq 0 かつ d_1 = d_2 ならば 1 回の移動で目標を達成できます。d_1 \neq d_2 である場合も、d_1 - d_2 が偶数なら、適当な k を使うことで 1 手で d_1 = d_2 にできて、残りは先程の場合に帰着できます。d_1 - d_2 が奇数の場合は、チェス盤上で色が異なる 2 つのマスを示している場合に対応していて、この場合は達成不可能です。
 

コード

class BishopMove
{
public:
	int howManyMoves(int r1, int c1, int r2, int c2)
	{
		const int d1 = abs( r1 - r2 ), d2 = abs( c1 - c2 );
		return ( d1 - d2 ) % 2 ? -1 : ( d1 || d2 ) + ( d1 != d2 );
	}
};