結果

問題 No.659 徘徊迷路
コンテスト
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2018-03-02 22:41:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 106 ms / 2,000 ms
コード長 1,441 bytes
コンパイル時間 938 ms
コンパイル使用メモリ 78,264 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-22 04:03:26
合計ジャッジ時間 2,467 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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