経路問題

今日のお題

座標1～8の8x8マスのチェス盤の上の座標が"(x y)(a b)"の形式で2つ与えられる。a > x, b > yは常に満たされる。(x y)から(a b)へ至る経路数を求めよ。

回答

import java.util.*;
import java.io.*;

class Main {
    public static String ChessboardTraveling(String str) {

        int x = str.charAt(1);
        int y = str.charAt(3);

        int a = str.charAt(6);
        int b = str.charAt(8);

        int len = (a - x) + (b - y);
        int right = a - x;

        int paths = 1;

        for (int i = len; len - right < i; i--) {
            paths *= i;
        }
        for (int i = 1; i <= right; i++) {
            paths /= i;
        }

        return Integer.toString(paths);
    }

    //mainやmainから呼ばれるメソッドのシグネチャはcoderbyteのお作法
    public static void main(String[] args) {
        // keep this function call here
        Scanner s = new Scanner(System.in);
        System.out.print(ChessboardTraveling(s.nextLine()));
    }
}

感想

小学校からお馴染みの経路問題。ここはcoderbyteなので座標は1から始まる。条件が厳しいのでparseも文字位置指定で十分。プログラムになれている人は再帰で書くのだろう。Eight queensを思い出す。

これがHardレベルというのはどうかと思うが、Easyとくらべると回答者の数がぐっと減り、テストケースで満点を取れていないようなコードが回答例に出てきたりする。これで金を取るのか。

今晩残りの時間はpermutationの計算について少し考えるのと、Java Collections Frameworkの勉強に費やす。