#include using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) #include #include using namespace std; template struct Matrix { vector> value; T init; Matrix(vector> vec, T init_) : init(init_), value(vec) {} Matrix(int h, int w, T init_) : init(init_), value(h, vector(w, init_)) {} Matrix operator*(Matrix& left) { Matrix res(value.size(), left[0].size(), init); for (int i = 0; i < value.size(); i++) { for (int k = 0; k < left.size(); k++) { for (int j = 0; j < left[0].size(); j++) { res[i][j] = (res[i][j] + value[i][k] * left[k][j]); } } } return res; } Matrix operator+(Matrix& left) { Matrix res = *this; for (int i = 0; i < res.size(); i++) { for (int j = 0; j < res[0].size(); j++) { res[i][j] += left[i][j]; } } return res; } Matrix operator*(T c) { Matrix res = *this; for (int i = 0; i < res.size(); i++) { for (int j = 0; j < res[0].size(); j++) { res[i][j] *= c; } } return res; } vector& operator[](int n) { return value[n]; } size_t size() { return value.size(); } Matrix operator^(long long n) { Matrix a = *this; Matrix res(a.size(), a.size(), init); for (int i = 0; i < a.size(); i++) { res[i][i] = 1; } while (n > 0) { if (n & 1) res = res * a; a = a * a; n >>= 1; } return res; } }; int R,C; i64 T; int sx,sy; int gx,gy; int fie[10][10]; int main(){ cin >> R >> C >> T; cin >> sy >> sx; cin >> gy >> gx; rep(i,0,R - 1){ string s; cin >> s; rep(j,0,C - 1){ fie[i][j] = s[j] == '.'; } } vector> m(100,vector(100,0)); int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; rep(i,1,R - 2){ rep(j,1,C - 2){ if(fie[i][j] == 0) continue; int cnt = 0; cnt += fie[i + 1][j]; cnt += fie[i - 1][j]; cnt += fie[i][j + 1]; cnt += fie[i][j - 1]; if(cnt == 0){ m[i * 10 + j][i * 10 + j] = 1; } else{ for(int d = 0;d < 4;d++){ if(fie[i + dx[d]][j + dy[d]] == 0) continue; m[(i + dx[d]) * 10 + (j + dy[d])][i * 10 + j] = 1.0 / cnt; } } } } Matrix m2(100,1,0); m2[sy * 10 + sx][0] = 1; cout << fixed << setprecision(10); cout << ((Matrix(m,0) ^ T) * m2)[gy * 10 + gx][0] << endl; }