SRM-425 250pt: CrazyBot

keyword

シミュレーション　確率　C++

問題概要

ロボットが東西南北の方向にある確率で移動する。n(<=14)ターン移動したときのパスが同じマスを通っていない確率を求める問題。

解法

nが小さいのがどう見ても怪しい。普通にDFSしたとき、既に訪ねたところには移動しないので最大でも分岐は3つ(初手を除く)。なのでシミュレーションしても計算量はO(3^n)以下で間に合う。あとは書くだけ。

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
double ps[4];
bool visited[200][200];
int n;

double getProbability(int _n, int east, int west, int south, int north) {
    int i,j;
    REP(i,200)REP(j,200) visited[i][j] = false;
    visited[100][100] = true;
    ps[0] = east/100.0;
    ps[1] = north/100.0;
    ps[2] = west/100.0;
    ps[3] = south/100.0;
    n = _n;
    return dfs(100,100,0);
}

double dfs(int y, int x, int depth){
    if(depth == n) return 1.0;
    double ret = 0.0;
    int k;
    REP(k,4){
        int ny = y + dy[k], nx = x + dx[k];
        if(visited[ny][nx]) continue;
        visited[ny][nx] = true;
        ret += dfs(ny,nx,depth+1)*ps[k];
        visited[ny][nx] = false;
    }
    return ret;
}