結果

問題 No.659 徘徊迷路
コンテスト
ユーザー roaris
提出日時 2019-11-02 21:30:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 68 ms / 2,000 ms
コード長 1,940 bytes
コンパイル時間 1,842 ms
コンパイル使用メモリ 175,048 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 23:20:13
合計ジャッジ時間 3,058 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<double> vec;
typedef vector<vec> mat;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

mat mat_mul(mat A, mat B) {
    mat C(A.size(), vec(B[0].size()));
    
    for (int i=0; i<A.size(); i++) {
        for (int j=0; j<B[0].size(); j++) {
            for (int k=0; k<A[0].size(); k++) {
                C[i][j] += A[i][k]*B[k][j];
            }
        }
    }
    
    return C;
}

mat mat_pow(mat A, int n) {
    mat res(A.size(), vec(A.size()));
    
    for (int i=0; i<A.size(); i++) {
        res[i][i] = 1;
    }
    
    while (n > 0) {
        if (n & 1) {
            res = mat_mul(A, res);
        }
        
        n >>= 1;
        A = mat_mul(A, A);
    }
    
    return res;
}

signed main() {
    int R, C, T;
    cin >> R >> C >> T;
    int Sx, Sy;
    cin >> Sx >> Sy;
    int Gx, Gy;
    cin >> Gx >> Gy;
    string B[R];
    
    for (int i=0; i<R; i++) {
        string Bi;
        cin >> Bi;
        B[i] = Bi;
    }
    
    mat Tr(R*C, vec(R*C));
    
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            if (B[i][j] == '#') {
                continue;
            }
            
            int cnt = 0;
            
            for (int k=0; k<4; k++) {
                if (B[i+dx[k]][j+dy[k]] == '.') {
                    cnt++;
                }
            }
            
            if (cnt == 0) {
                Tr[C*i+j][C*i+j] = 1.0;
                continue;
            }
            
            double p = 1.0/cnt;

            for (int k=0; k<4; k++) {
                if (B[i+dx[k]][j+dy[k]] == '.') {
                    Tr[C*(i+dx[k])+j+dy[k]][C*i+j] = p;
                }
            }
        }
    }
    
    mat before(R*C, vec(1));
    before[C*Sx+Sy][0] = 1.0;
    mat after = mat_mul(mat_pow(Tr, T), before);
    
    cout << setprecision(10) << after[C*Gx+Gy][0] << endl;
}
0