【TopCoder】SRM425 DIV2 Lv.2

問題文概略

ロボットがランダムに東西南北に動く。n回ランダムに動くとき、一度通った道を通らずに動き続ける確率を求める。

書いたコード

import java.util.Arrays;

public class CrazyBot {
    //自分のいる場所
    boolean[][] grid = new boolean[100][100];
    //一歩動くときの座標の変化(eastならvx[1], vy[1])
    int vx[] = {1, -1, 0, 0};
    int vy[] = {0, 0, 1, -1};
    //それぞれの方向に動く確率
    double[] prob = new double[4];

    public double getProbability(int n, int east, int west, int south, int north) {

        prob[0] = east / 100.0;
        prob[1] = west / 100.0;
        prob[2] = south / 100.0;
        prob[3] = north / 100.0;
        //初期位置を座標の真ん中に持ってきている
        return dfs(50, 50, n);
    }

    double dfs(int x, int y, int n) {
        //既に訪れている場所にいくと0を返す
        if(grid[x][y]) return 0;
        if(n == 0) return 1;

        grid[x][y] = true;
        double ret = 0;
        for(int i = 0; i < 4; i++) {
            //east, west, north, southの順にロボットを動かす
            ret += dfs(x + vx[i], y + vy[i], n-1) * prob[i];
            //System.out.println(ret);
        }
        grid[x][y] = false;
        return ret;
    }
}

雑感

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド

上記の本に載っていた問題。 ぼんやり理解しているだけなのでもう何問か深さ優先探索を使った問題を解いてみないと。