結果

問題 No.659 徘徊迷路
ユーザー imulanimulan
提出日時 2018-03-16 05:19:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 1,921 bytes
コンパイル時間 1,784 ms
コンパイル使用メモリ 176,232 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-21 14:08:58
合計ジャッジ時間 3,079 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 15 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 22 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 25 ms
5,248 KB
testcase_09 AC 56 ms
5,248 KB
testcase_10 AC 67 ms
5,248 KB
testcase_11 AC 65 ms
5,248 KB
testcase_12 AC 14 ms
5,248 KB
testcase_13 AC 56 ms
5,248 KB
testcase_14 AC 56 ms
5,248 KB
testcase_15 AC 66 ms
5,248 KB
testcase_16 AC 66 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using vd = vector<double>;
using mat = vector<vd>;

mat mul(const mat &a, const mat &b){
    int n = a.size();
    mat c(n,vd(n));
    rep(i,n)rep(j,n)rep(k,n) c[i][j] += a[i][k]*b[k][j];
    return c;
}

vd mul(const mat &a, const vd &v){
    int n = a.size();
    vd ret(n);
    rep(i,n)rep(j,n) ret[i] += a[i][j]*v[j];
    return ret;
}

mat pow(const mat &a, int x){
    int n = a.size();

    mat ret(n,vd(n));
    rep(i,n) ret[i][i] = 1;

    mat p(a);
    while(x){
        if(x&1) ret = mul(ret,p);
        p = mul(p,p);
        x>>=1;
    }
    return ret;
}

const int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

int main(){
    int h,w,t;
    cin >>h >>w >>t;
    int sy,sx,gy,gx;
    cin >>sy >>sx >>gy >>gx;

    vector<string> b(h);
    rep(i,h) cin >>b[i];

    auto ID = [&](int y, int x){ return y*w+x; };

    int n = h*w;
    mat A(n,vd(n));

    rep(i,h)rep(j,w)if(b[i][j]=='.'){
        int ct = 0;
        rep(d,4){
            int ny = i+dy[d], nx = j+dx[d];
            ct += (b[ny][nx]=='.');
        }

        if(ct==0){
            A[ID(i,j)][ID(i,j)] = 1;
        }
        else{
            double p = 1.0/ct;
            rep(d,4){
                int ny = i+dy[d], nx = j+dx[d];
                if(b[ny][nx]=='.') A[ID(ny,nx)][ID(i,j)] = p;
            }
        }
    }

    vd start(n);
    start[ID(sy,sx)] = 1;

    vd ans = mul(pow(A,t), start);

    printf("%.10f\n", ans[ID(gy,gx)]);
    return 0;
}
0