結果

問題 No.659 徘徊迷路
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2018-03-02 22:41:23
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 1,441 bytes
コンパイル時間 1,249 ms
コンパイル使用メモリ 76,648 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-04 04:31:51
合計ジャッジ時間 3,046 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

const int N=10;
string b[N];

typedef vector<double> vd;

vector<vd> mul(const vector<vd> &a,const vector<vd> &b){
  int A=a.size();
  vector<vd> ret(A, vd(A));
  rep(i,A){
    rep(j,A){
      rep(k,A){
	ret[i][j]+=a[i][k]*b[k][j];
      }
    }
  }
  return ret;
}

vector<vd> pow(const vector<vd> &a,lint e){
  int A=a.size();
  vector<vd> cur(A,vd(A,0));
  rep(i,A)cur[i][i]=1;
  for(int i=63;i>=0;--i){
    cur=mul(cur,cur);
    if(e&1LL<<i)cur=mul(cur,a);
  }
  return cur;
}


int main(){
  int r,c;
  lint t;
  cin>>r>>c>>t;
  int sx,sy,gx,gy;
  cin>>sx>>sy>>gx>>gy;
  rep(i,r){
    cin>>b[i];
  }
  int dx[4]={1,0,-1,0};
  int dy[4]={0,1,0,-1};
  bool ok=0;
  rep(d,4){
    int nx=sx+dx[d];
    int ny=sy+dy[d];
    if(b[nx][ny]!='#')ok=1;
  }
  if(!ok){
    cout<<(sx==gx&&sy==gy?1:0)<<endl;
    return 0;
  }
  vector<vd> trans(r*c,vd(r*c,0));
  rep(i,r){
    rep(j,c){
      if(b[i][j]=='#')continue;
      int cnt=0;
      rep(d,4){
	int nx=i+dx[d];
	int ny=j+dy[d];
	if(b[nx][ny]!='#'){
	  cnt++;
	}
      }
      if(cnt>0){
	rep(d,4){
	  int nx=i+dx[d];
	  int ny=j+dy[d];
	  if(b[nx][ny]!='#'){
	    trans[nx*c+ny][i*c+j]=1.0/cnt;
	  }
	}
      }
    }
  }
  vector<vd> ex=pow(trans,t);
  printf("%.15f\n",ex[gx*c+gy][sx*c+sy]);
}
0