TopCoder SRM 628, Division 2, Level 1 : BishopMove

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13280&rd=16009

問題概要

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

解法

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