TopCoder - SRM 425 DIV 2: 500

SRM 425 DIV 1: 250と同一問題。これ難しかった。とりあえずやっつけでやってみた。コードはこちら。312点…。問題は、東西南北自由に動き回るロボットが指定回数動いたときに、同じ地点に戻ってこない確率を求めるというもの。

public class CrazyBot {
  double we, ww, ws, wn;
  double total = 0.0;
  public double getProbability(
    int n,
    int east,
    int west,
    int south,
    int north) {
    int sum = east + west + south + north;
    we = east * 1.0 / sum;
    ww = west * 1.0 / sum;
    ws = south * 1.0 / sum;
    wn = north * 1.0 / sum;
    boolean flag[][] = new boolean[n*2+1][n*2+1];
    move(flag, n, n, 1.0, n);
    return total;
  }
  public void move(
    boolean flag[][],
    int x, int y, double p, int n) {
    if (flag[x][y]) {
      return;
    }
    if (n < 0) {
      return;
    }
    if (n == 0) {
      total += p;
      return;
    }
    flag[x][y] = true;
    if (we > 0.0) {
      move(flag, x+1, y, p * we, n-1);
    }
    if (ww > 0.0) {
      move(flag, x-1, y, p * ww, n-1);
    }
    if (ws > 0.0) {
      move(flag, x, y-1, p * ws, n-1);
    }
    if (wn > 0.0) {
      move(flag, x, y+1, p * wn, n-1);
    }
    flag[x][y] = false;
  }
}