徘徊迷路 [yukicoder No.659] - はまやんはまやんはまやん

前提知識

行列累乗

解法

この問題は行列累乗の初心者向け問題には向かないので、もし知らない場合は他の問題で仕組みを理解することをおすすめする。
dpで解く。
「dp[y*W+x] := マス(x,y)に到着する確率」
これを遷移確率が書かれた隣接行列を使って更新していく。
　
隣接行列は隣接する2つの頂点について「M[yy*W+xx][y*W+x] = 確率」として構成する。
あとは、これを行列累乗を使ってT乗して、最後にdpを更新して答える。
遷移先が存在しない場合は、自分に辺を貼る必要があるので注意。

int H, W, T, SY, SX, GY, GX;
string B[10];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> T >> SY >> SX >> GY >> GX;
    rep(y, 0, H) cin >> B[y];

    Vec v(100);
    v[SY * 10 + SX] = 1;
    
    Mat m(100, Vec(100));
    rep(y, 0, H) rep(x, 0, W) if(B[y][x] == '.'){
        int cnt = 0;
        rep(i, 0, 4) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (0 <= xx and xx < W and 0 <= yy and yy < H) {
                if (B[yy][xx] == '.') cnt++;
            }
        }

        if (cnt == 0) {
            m[y * 10 + x][y * 10 + x] = 1;
            continue;
        }

        double p = 1.0 / (double)cnt;
        rep(i, 0, 4) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (0 <= xx and xx < W and 0 <= yy and yy < H) if (B[yy][xx] == '.') {
                m[yy * 10 + xx][y * 10 + x] = p;
            }
        }
    }

    v = mulMatVec(fastpow(m, T), v);

    double ans = v[GY * 10 + GX];
    printf("%.10f\n", ans);
}