結果
問題 | No.659 徘徊迷路 |
ユーザー |
|
提出日時 | 2020-03-04 13:41:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 1,185 bytes |
コンパイル時間 | 634 ms |
コンパイル使用メモリ | 73,172 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 00:11:24 |
合計ジャッジ時間 | 1,883 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 12 |
コンパイルメッセージ
main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 9 | main() | ^~~~
ソースコード
#include<iostream> #include<iomanip> using namespace std; int R,C,T; int sx,sy,gx,gy; string S[10]; double A[100][100],E[100][100],tmp[100][100]; int d[4]={1,0,-1}; main() { cin>>R>>C>>T>>sx>>sy>>gx>>gy; int s=sx*C+sy,g=gx*C+gy; for(int i=0;i<R;i++)cin>>S[i]; int N=R*C; for(int i=0;i<N;i++)E[i][i]=1; for(int x=0;x<R;x++)for(int y=0;y<C;y++) { if(S[x][y]=='#')continue; int cnt=0; for(int r=0;r<4;r++) { int tx=x+d[r],ty=y+d[r^1]; if(S[tx][ty]=='.')cnt++; } if(cnt==0) { A[x*C+y][x*C+y]+=1; } else { for(int r=0;r<4;r++) { int tx=x+d[r],ty=y+d[r^1]; if(S[tx][ty]=='.')A[tx*C+ty][x*C+y]+=1./cnt; } } } while(T) { if(T&1) { for(int i=0;i<N;i++)for(int j=0;j<N;j++)tmp[i][j]=0; for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<N;k++)tmp[i][j]+=E[i][k]*A[k][j]; for(int i=0;i<N;i++)for(int j=0;j<N;j++)E[i][j]=tmp[i][j]; } T>>=1; for(int i=0;i<N;i++)for(int j=0;j<N;j++)tmp[i][j]=0; for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<N;k++)tmp[i][j]+=A[i][k]*A[k][j]; for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<N;k++)A[i][j]=tmp[i][j]; } cout<<fixed<<setprecision(15)<<E[g][s]<<endl; }