Hatena::Grouptopcoder

Akenshoの日記

2014-07-22

SRM 628(Div2)

23:45 | はてなブックマーク - SRM 628(Div2) - Akenshoの日記

SRM 628: xx- 0pts.

4~5ヶ月ぶりにSRMに参加してみた。

250と500の両方に落ちたので、0完だった。(これが「太陽が生える」というものなのか。)

とても辛いので、真面目に問題を考察して、二度と血の涙を流さないように、僕みたいな競技者の助けになるように、詳細を記す。

250 BishopMove

概要
  1. あなたはチェスのビショップに興味を持っている。
    • チェス盤は8x8で、(0, 0)から(7, 7)まで座標が割り振られている。
    • ビショップは将棋の「角」と同じで、斜め4方向のうち1つの方向へ、チェス盤の範囲外になるまで、移動することができる。
  2. いま、何も駒が置かれていないチェス盤の座標、(r1, c1)にビショップを置く。
  3. このビショップを目的地(r2, c2)へ動かしたいとき、最小で何回の移動が必要か?
    • もし、移動できない場合は -1 を出力せよ。
方針
  1. 移動できないとき
  2. 最小移動回数が0のとき
    • 初期位置と目的地が同じ座標
  3. 最小移動回数が1のとき
    • 初期位置の対角線上に目的地が存在する
  4. 最小移動回数が2のとき
    • 上記3通り以外は2回の移動で到達できる。
コード
import java.util.ArrayList;
import java.util.HashSet;

public class BishopMove {
	public int howManyMoves(int r1, int c1, int r2, int c2) {
		if( (Math.abs(r1 - r2) + Math.abs(c1 - c2)) % 2 == 1 ) return -1;
		if( r1 == r2 && c1 == c2 ) return 0;		
		HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
		int[] dx = {1, 1, -1, -1}, dy = {1, -1, -1, 1};
		for(int i = 0; i < 4; i++){
			int nx = c1, ny = r1;
			while( true ){
				nx += dx[i];
				ny += dy[i];
				if( 0 <= nx && nx <= 7 && 0 <= ny && ny <= 7 ){
					ArrayList<Integer> list = new ArrayList<Integer>();
					list.add(nx);list.add(ny);
					set.add(list);
				}else{
					break;
				}
			}			
		}
		ArrayList<Integer> init = new ArrayList<Integer>();
		init.add(c2);init.add(r2);
		return set.contains(init) ? 1 : 2;
	}
}
コードの詳細
  • マンハッタン距離の算出
if( (Math.abs(r1 - r2) + Math.abs(c1 - c2)) % 2 == 1 ) return -1;
    • 絶対値の計算は、Math.abs で可能。
    • 偶奇の判定は剰余を求めることで可能。
  • 初期位置と目的地が同じ座標かどうかを判定
if( r1 == r2 && c1 == c2 ) return 0;			
    • 単にx座標とy座標が一致しているかを調べているだけ。
  • 初期位置の対角線上に目的地が存在するかどうかを判定
    • 「初期位置の対角線上にある座標」を集合 HashSet で管理する。
    • Hashsetの要素になるのは ArrayList で、ArrayList の型は Integer
int[] dx = {1, 1, -1, -1}, dy = {1, -1, -1, 1};
    • dxとdyは方向ベクトル。
nx += dx[i];
ny += dy[i];
    • 方向ベクトルに対してforループを回し、更新した座標を示すnxとnyに値を保存していく。
if( 0 <= nx && nx <= 7 && 0 <= ny && ny <= 7 )
    • 更新したnxとnyがチェス盤の外にでるかを判定し、
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(nx);
list.add(ny);
    • チェス盤の範囲内なら座標を list に入れる。
set.add(list);
    • さらに、座標集合 set に list を保存する。
    • while ループを抜けるタイミングは、nx と ny がチェス盤の範囲外にでたとき。
    • ループを抜けると、次の方向ベクトルに対して同様の処理が始まる。
ArrayList<Integer> init = new ArrayList<Integer>();
init.add(c2);
init.add(r2);
    • init には目的地(c2, r2)を入れる。(変数名を init ではなく、destination にするべきだった)
return set.contains(init) ? 1 : 2;
    • 座標集合 set に、目的地である init が含まれているかを判定している。
    • 含まれているなら、目的地は初期位置の対角線上に存在するので 1 回の移動で到達できる。
    • そうでないならば、2回の移動で到達できる。