結果

問題 No.659 徘徊迷路
ユーザー TsReaperTsReaper
提出日時 2018-03-26 16:26:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 1,698 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 35,868 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-09-07 12:43:20
合計ジャッジ時間 1,448 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <cmath>
#define EPS 1e-12

int n,m,C,SI,SJ,FI,FJ;
char MAP[15][15];

short dir[4][2] = {0,1,1,0,-1,0,0,-1};

struct Rect
{
    int n,m;
    double v[110][110];
    Rect():n(0),m(0) { memset(v,0,sizeof(v)); }
}K,X;

Rect IRect(int siz)
{
    int i;
    Rect ret;

    ret.n = ret.m = siz;
    for(i=0;i<siz;i++) ret.v[i][i] = 1;
    return ret;
}

Rect operator * (Rect &a,Rect &b)
{
    int i,j,k;
    Rect ret;

    ret.n = a.n; ret.m = b.m;
    for(i=0;i<a.n;i++) for(j=0;j<a.m;j++) if(fabs(a.v[i][j]) > EPS)
        for(k=0;k<b.m;k++) ret.v[i][k] += a.v[i][j] * b.v[j][k];
    return ret;
}

Rect power(Rect &a,int b)
{
    Rect base = a,y = IRect(a.n);
    for(;b;b>>=1)
    {
        if(b&1) y = y * base;
        base = base * base;
    }
    return y;
}

int id(int a,int b)
{
    return (a-1)*(m-2) + (b-1);
}

void input()
{
    int i;
    scanf("%d%d%d%d%d%d%d",&n,&m,&C,&SI,&SJ,&FI,&FJ);
    for(i=0;i<n;i++) scanf("%s",MAP[i]);
}

void build()
{
    int i,j,k,x,ii,jj,cnt;

    K.n = K.m = (n-2)*(m-2);
    for(i=1,x=0;i<n-1;i++) for(j=1;j<m-1;j++,x++)
    {
        cnt = 0;
        for(k=0;k<4;k++)
        {
            ii = i + dir[k][0]; jj = j + dir[k][1];
            cnt += (MAP[ii][jj] == '.');
        }

        if(!cnt) K.v[x][x] = 1;
        else for(k=0;k<4;k++)
        {
            ii = i + dir[k][0]; jj = j + dir[k][1];
            if(MAP[ii][jj] == '.') K.v[id(ii,jj)][x] = 1.0 / cnt;
        }
    }

    X.n = (n-2)*(m-2); X.m = 1;
    X.v[id(SI,SJ)][0] = 1;
}

double work()
{
    K = power(K,C);
    return (K*X).v[id(FI,FJ)][0];
}

int main()
{
    input();
    build();
    printf("%.12f",work());
    return 0;
}
0