結果
問題 | No.659 徘徊迷路 |
ユーザー |
![]() |
提出日時 | 2021-03-22 10:33:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,447 ms / 2,000 ms |
コード長 | 1,870 bytes |
コンパイル時間 | 5,916 ms |
コンパイル使用メモリ | 289,760 KB |
最終ジャッジ日時 | 2025-01-19 21:00:00 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 12 |
ソースコード
#include "bits/stdc++.h" #include <boost/numeric/ublas/matrix.hpp> #define MOD 1000000007 #define rep(i, n) for(ll i=0; i < (n); i++) #define rrep(i, n) for(ll i=(n)-1; i >=0; i--) #define ALL(v) v.begin(),v.end() #define rALL(v) v.rbegin(),v.rend() #define FOR(i, j, k) for(ll i=j;i<k;i++) #define debug_print(var) cerr << #var << "=" << var <<endl; #define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" " #define fi first #define se second using namespace std; using namespace boost::numeric::ublas; typedef long long int ll; typedef std::vector<ll> llvec; typedef std::vector<double> dvec; typedef pair<ll, ll> P; typedef long double ld; struct edge{ll x, c;}; /************************************** ** A main function starts from here ** ***************************************/ int main(){ ll R, C, T; cin >> R >> C >> T; matrix<ld> A(R*C, R*C); matrix<ld> e(R*C, R*C); rep(i, R*C)e(i, i) = 1.0; P s, g; cin >> s.fi >> s.se; cin >> g.fi >> g.se; std::vector<string> B(R); rep(i, R)cin >> B[i]; auto ind = [R, C](ll i, ll j){return i*C + j;}; rep(i, R){ rep(j, C){ ll cnt = 0; if(B[i][j]!='#'){ if(i-1>0 and B[i-1][j]!='#')cnt++; if(i+1<R and B[i+1][j]!='#')cnt++; if(j-1>0 and B[i][j-1]!='#')cnt++; if(j+1<C and B[i][j+1]!='#')cnt++; if(i-1>0 and B[i-1][j]!='#')A(ind(i, j), ind(i-1, j))+=1./cnt; if(i+1<R and B[i+1][j]!='#')A(ind(i, j), ind(i+1, j))+=1./cnt; if(j-1>0 and B[i][j-1]!='#')A(ind(i, j), ind(i, j-1))+=1./cnt; if(j+1<C and B[i][j+1]!='#')A(ind(i, j), ind(i, j+1))+=1./cnt; if(cnt==0)A(ind(i, j), ind(i, j))=1; } } } while(T>0){ if(T%2==1){ e = prod(A, e); } A = prod(A,A); T/=2; } //s.fi--;s.se--; //g.fi--;g.se--; cout << e(ind(s.fi, s.se), ind(g.fi, g.se))<<endl; return 0; }