#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define Rep(b, e, i) for(int i = b; i <= e; i++) #define Repr(e, b, i) for(int i = e; i >= b; i--) #define rep(n, i) Rep(0, n-1, i) #define repr(n, i) Repr(n-1, 0, i) #define all(v) (v).begin(), (v).end() #define pb(v) push_back(v) #define uniq(v) (v).erase(unique(all(v)),(v).end()) #define bitcnt(x) __builtin_popcount(x) #define fst first #define snd second #define Pqaz(T) priority_queue,greater> #define Pqza(T) priority_queue #define put(x) cout << x; #define putsp(x) cout << x << ' '; #define putln(x) cout << x << endl; #define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0); typedef long long ll; typedef pair llP; typedef pair intP; typedef complex comp; //vector の中身を出力 template ostream &operator<<(ostream &o,const vector&v) {o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")< Vec; typedef vector Mat; //A * B = C Mat mul(const Mat &A, const Mat &B) { //大前提 assert((int)A[0].size() == (int)B.size()); Mat C((int)A.size(), Vec((int)B[0].size(), 0)); //メモリへのアクセス的にこうしたほうが早いのです rep((int)A.size(), i) rep((int)B.size(), k) rep((int)B[0].size(), j) { C[i][j] += A[i][k] * B[k][j]; } return C; } // v' = A * v //オーバーロードしているんです!!!!!!!!!!!! Vec mul(const Mat &A, const Vec &v) { //大前提 assert((int)A[0].size() == (int)v.size()); Vec nv((int)A.size(), 0); rep((int)A.size(), i) rep((int)v.size(), j) { nv[i] += A[i][j] * v[j]; } return nv; } // A ^ N Mat mpow(Mat A, int N) { //大前提 assert((int)A[0].size() == (int)A.size() && N > 0); Mat Res((int)A.size(), Vec((int)A.size(), 0)); // A ^ 0 = E rep((int)A.size(), i) { Res[i][i] = 1; } while(N) { if (N & 1) { Res = mul(Res, A); } A = mul(A, A); N >>= 1; } return Res; } //************************************************************************// int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; void solve(void){ int R, C, T, sy, sx, gy, gx; cin >> R >> C >> T >> sy >> sx >> gy >> gx; vector maze(R); rep(R, i) cin >> maze[i]; int m = R*10+C; Mat M(m, Vec(m, 0)); rep(R, y) rep(C, x) { if (maze[y][x] == '#') { continue; } int cnt = 0; rep(4, d) { int ny = y + dy[d], nx = x + dx[d]; if (0 <= ny && ny < R && 0 <= nx && nx < C) { cnt += maze[ny][nx] == '.'; } } if (!cnt) { M[y*10+x][y*10+x] = 1; continue; } double p = 1. / cnt; rep(4, d) { int ny = y + dy[d], nx = x + dx[d]; if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[y][x] == '.') { M[10*ny+nx][10*y+x] = p; } } } Vec V(m); rep(R, y) rep(C, x) { V[10*y+x] = (sy==y&&sx==x); } V = mul(mpow(M, T), V); cout << setprecision(12) << V[gy*10+gx] << endl; } int main(void){ solve(); //cout << "yui(*-v・)yui" << endl; return 0; }