/* -*- coding: utf-8 -*- * * 659.cc: No.659 徘徊迷路 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_H = 10; const int MAX_W = 10; const int MAX_N = (MAX_H - 2) * (MAX_W - 2); const int dxs[] = { 1, 0, -1, 0 }, dys[] = { 0, -1, 0, 1 }; /* typedef */ typedef double vec[MAX_N]; typedef vec mat[MAX_N]; /* global variables */ string flds[MAX_H]; /* subroutines */ inline void initvec(int n, vec a) { fill(a, a + n, 0.0); } inline void initmat(int n, mat a) { for (int i = 0; i < n; i++) initvec(n, a[i]); } inline void unitmat(int n, mat a) { initmat(n, a); for (int i = 0; i < n; i++) a[i][i] = 1.0; } inline void copymat(int n, const mat a, mat b) { memcpy(b, a, sizeof(mat)); } inline void addmat(int n, const mat a, const mat b, mat c) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) c[i][j] = a[i][j] + b[i][j]; } inline void mulmat(int n, const mat a, const mat b, mat c) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { c[i][j] = 0.0; for (int k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } } inline void powmat(int n, const mat a, int b, mat c) { mat s, t; copymat(n, a, s); unitmat(n, c); while (b > 0) { if (b & 1) { mulmat(n, c, s, t); copymat(n, t, c); } mulmat(n, s, s, t); copymat(n, t, s); b >>= 1; } } inline void mulmatvec(int n, const mat a, const vec b, vec c) { for (int i = 0; i < n; i++) { c[i] = 0.0; for (int j = 0; j < n; j++) c[i] += a[i][j] * b[j]; } } inline int xy2p(int x, int y, int w) { return (y - 1) * (w - 2) + (x - 1); } /* main */ int main() { int h, w, t; cin >> h >> w >> t; int sy, sx, gy, gx; cin >> sy >> sx >> gy >> gx; for (int y = 0; y < h; y++) cin >> flds[y]; int n = (h - 2) * (w - 2); mat a; initmat(n, a); for (int y = 1; y < h - 1; y++) for (int x = 1; x < w - 1; x++) if (flds[y][x] == '.') { int cnt = 0, p = xy2p(x, y, w); bool bs[4] = { false }; for (int di = 0; di < 4; di++) { int vx = x + dxs[di], vy = y + dys[di]; if (flds[vy][vx] == '.') cnt++, bs[di] = true; } if (cnt == 0) a[p][p] = 1.0; else for (int di = 0; di < 4; di++) if (bs[di]) { int vx = x + dxs[di], vy = y + dys[di], vp = xy2p(vx, vy, w); a[p][vp] = 1.0 / cnt; } } mat c; powmat(n, a, t, c); int sp = xy2p(sx, sy, w), gp = xy2p(gx, gy, w); printf("%.16lf\n", c[sp][gp]); return 0; }