結果

問題 No.659 徘徊迷路
コンテスト
ユーザー TsReaper
提出日時 2018-03-26 16:26:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,698 bytes
コンパイル時間 588 ms
コンパイル使用メモリ 33,920 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-25 06:47:45
合計ジャッジ時間 1,370 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void input()’:
main.cpp:58:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |     scanf("%d%d%d%d%d%d%d",&n,&m,&C,&SI,&SJ,&FI,&FJ);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:59:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |     for(i=0;i<n;i++) scanf("%s",MAP[i]);
      |                      ~~~~~^~~~~~~~~~~~~

ソースコード

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