#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef long long int ll; #define debug(v) {printf("L%d %s > ",__LINE__,#v);cout<<(v)< ",__LINE__,#v);for(auto e:(v)){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout< ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } template T& maxset(T& to, const T& val) { return to = max(to, val); } template T& minset(T& to, const T& val) { return to = min(to, val); } void bye(string s, int code = 0) { cout << s << endl; exit(code); } mt19937_64 randdev(8901016); inline ll rand_range(ll l, ll h) { return uniform_int_distribution(l, h)(randdev); } #if defined(_WIN32) || defined(_WIN64) #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #elif defined(__GNUC__) #else #define getchar_unlocked getchar #define putchar_unlocked putchar #endif namespace { #define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E) class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(string& var) { int cc = getchar_unlocked(); for (; !isvisiblechar(cc); cc = getchar_unlocked()); for (; isvisiblechar(cc); cc = getchar_unlocked()) var.push_back(cc); return *this; } template void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; } }; class MaiPrinter { public: template void output_integer(T var) { if (var == 0) { putchar_unlocked('0'); return; } if (var < 0) putchar_unlocked('-'), var = -var; char stack[32]; int stack_p = 0; while (var) stack[stack_p++] = '0' + (var % 10), var /= 10; while (stack_p) putchar_unlocked(stack[--stack_p]); } inline MaiPrinter& operator<<(char c) { putchar_unlocked(c); return *this; } inline MaiPrinter& operator<<(int var) { output_integer(var); return *this; } inline MaiPrinter& operator<<(long long var) { output_integer(var); return *this; } inline MaiPrinter& operator<<(char* str_p) { while (*str_p) putchar_unlocked(*(str_p++)); return *this; } inline MaiPrinter& operator<<(const string& str) { const char* p = str.c_str(); const char* l = p + str.size(); while (p < l) putchar_unlocked(*p++); return *this; } template void join(IT begin, IT end, char sep = '\n') { for (auto it = begin; it != end; ++it) *this << *it << sep; } }; } MaiScanner scanner; MaiPrinter printer; template // typedef double T; class Matrix { public: size_t height_, width_; valarray data_; Matrix(size_t height, size_t width) :height_(height), width_(width), data_(height*width) {} Matrix(size_t height, size_t width, const valarray& data) :height_(height), width_(width), data_(data) {} inline T& operator()(size_t y, size_t x) { return data_[y*width_ + x]; } inline T operator() (size_t y, size_t x) const { return data_[y*width_ + x]; } inline T& at(size_t y, size_t x) { return data_[y*width_ + x]; } inline T at(size_t y, size_t x) const { return data_[y*width_ + x]; } inline void resize(size_t h, size_t w) { height_ = h; width_ = w; data_.resize(h*w); } inline void resize(size_t h, size_t w, T val) { height_ = h; width_ = w; data_.resize(h*w, val); } inline void fill(T val) { data_ = val; } Matrix& setDiag(T val) { for (size_t i = 0, en = min(width_, height_); i < en; ++i)at(i, i) = val; return *this; } void print(ostream& os) { os << "- - -" << endl; // << setprecision(3) for (size_t y = 0; y < height_; ++y) { for (size_t x = 0; x < width_; ++x) { os << setw(7) << at(y, x) << ' '; }os << endl; } } valarray> to_valarray() const { valarray> work(height_); for (size_t i = 0; i < height_; ++i) { auto &v = work[i]; v.resize(height_); for (size_t j = 0; j < width_; ++j) v[j] = at(i, j); } return work; } // mathematics Matrix pow(long long); double det() const; T tr(); Matrix& transpose_self(); Matrix transpose() const; struct LU { size_t size; vector pivot; vector elem; }; }; // IO template inline ostream& operator << (ostream& os, Matrix mat) { mat.print(os); return os; } // 掛け算 template Matrix multiply(const Matrix& mat1, const Matrix& mat2) { assert(mat1.width_ == mat2.height_); Matrix result(mat1.height_, mat2.width_); for (size_t i = 0; i < mat1.height_; i++) { for (size_t j = 0; j < mat2.width_; j++) { for (size_t k = 0; k < mat1.width_; k++) { result(i, j) += mat1(i, k) * mat2(k, j); } } } return result; } template valarray multiply(const Matrix& mat1, const valarray& vec2) { assert(mat1.width_ == vec2.size()); valarray result(mat1.height_); for (size_t i = 0, j; i < mat1.height_; i++) { for (j = 0; j < mat1.width_; j++) { result[i] += mat1(i, j) * vec2[j]; } } return result; } template inline Matrix& operator*=(Matrix& mat1, Matrix& mat2) { mat1 = multiply(mat1, mat2); return mat1; } template inline Matrix operator*(Matrix& mat1, Matrix& mat2) { return multiply(mat1, mat2); } // スカラー template inline Matrix& operator+=(Matrix& mat, T val) { mat.data_ += val; return mat; } template inline Matrix& operator*=(Matrix& mat, T val) { mat.data_ *= val; return mat; } template inline Matrix& operator/=(Matrix& mat, T val) { mat.data_ /= val; return mat; } template inline Matrix& operator^=(Matrix& mat, T val) { mat.data_ ^= val; return mat; } // 行列 template inline Matrix& operator+=(Matrix& mat1, Matrix& mat2) { mat1.data_ += mat2.data_; return mat1; } template inline Matrix operator+(Matrix& mat1, Matrix& mat2) { return Matrix(mat1.height_, mat1.width_, mat1.data_ + mat2.data_); } template Matrix Matrix::pow(long long p) { assert(height_ == width_); Matrix a = *this; Matrix b(height_, height_); b.setDiag(1); while (0 < p) { if (p % 2) { b *= a; } a *= a; p /= 2; } return b; } namespace hoge{ int height, width, turn; int starty, startx, goaly, goalx; int field[10][10]; int main() { scanner >> height >> width >> turn; scanner >> starty >> startx >> goaly >> goalx; Matrix matF(100, 100); matF.fill(0); repeat(i, height) { string line; scanner >> line; repeat(j, width) { field[i][j] = line[j] == '.'; } } //debugaa(field, height, width); repeat(i, 10) { repeat(j, 10) { if (!field[i][j]) continue; int id = i * 10 + j; double sum = field[i - 1][j] + field[i + 1][j] + field[i][j - 1] + field[i][j + 1]; if (sum == 0) { matF(id, id) = 1.0; continue; } // if (field[i - 1][j]) // matF(id, id - 10) = 1.0 / sum, cout << id - 10 << endl; // if (field[i + 1][j]) // matF(id, id + 10) = 1.0 / sum, cout << id + 10 << endl; // if (field[i][j - 1]) // matF(id, id - 1) = 1.0 / sum, cout << id - 1 << endl; // if (field[i][j + 1]) // matF(id, id + 1) = 1.0 / sum, cout << id + 1 << endl; //cout << id << " " << field[i][j-1] << field[i-1][j] << field[i][j+1] << field[i+1][j] << endl; if (field[i - 1][j]) matF(id - 10, id) = 1.0 / sum; if (field[i + 1][j]) matF(id + 10, id) = 1.0 / sum; if (field[i][j - 1]) matF(id - 1, id) = 1.0 / sum ; if (field[i][j + 1]) matF(id + 1, id) = 1.0 / sum ; } } auto matFt = matF.pow(turn); //cout << matFt << endl; //cout < vec1(100, 1); vec1.fill(0); vec1(starty * 10 + startx-1, 1) = 1.0; auto vect = matFt * vec1; double ans = vect(goaly * 10 + goalx-1, 1); // cout << vect(starty * 10 + startx - 1, 1) << endl; // cout << vect(starty * 10 + startx + 1, 1) << endl; // cout << starty * 10 + startx - 1 << endl; // // repeat(i, height) { // repeat(j, width) { // cout << setw(6) << vec1(i * 10 + j, 1) << " "; // } // cout << endl; // } // cout << endl; // repeat(i, height) { // repeat(j, width) { // cout << setw(6) << vect(i * 10 + j, 1) << " "; // } // cout << endl; // } printf("%.10f\n", ans); return 0; } } int main(){ return hoge::main();}