結果

問題 No.659 徘徊迷路
ユーザー imulanimulan
提出日時 2018-03-16 05:19:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 1,921 bytes
コンパイル時間 3,616 ms
コンパイル使用メモリ 173,716 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-23 11:36:05
合計ジャッジ時間 3,055 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 15 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 20 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 24 ms
4,376 KB
testcase_09 AC 56 ms
4,380 KB
testcase_10 AC 64 ms
4,376 KB
testcase_11 AC 64 ms
4,376 KB
testcase_12 AC 13 ms
4,380 KB
testcase_13 AC 58 ms
4,376 KB
testcase_14 AC 56 ms
4,380 KB
testcase_15 AC 65 ms
4,380 KB
testcase_16 AC 65 ms
4,380 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