#include using namespace std; #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL 9223372036854775 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define MOD 10000 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double #define int long long #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(a) begin((a)), end((a)) #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define MP make_pair #define SZ(a) int((a).size()) template class Matrix { public: Matrix(int r, int c) { mat.clear(); for(int i = 0; i < r; i++) { mat.push_back(vector()); mat[i].resize(c); } } vector& operator[] (int r) { return mat[r]; } void print() const { for(int i = 0; i < mat.size(); i++) { for(int j = 0; j < mat[i].size(); j++) { cerr << mat[i][j] << " "; } cerr << endl; } } unsigned int getR() const { return mat.size(); } unsigned int getC() const { return mat[0].size(); } Matrix operator + (Matrix& matrix) { Matrix ret(this->getR(), this->getC()); for(int r = 0; r < matrix.getR(); r++) { for(int c = 0; c < matrix.getC(); c++) { ret[r][c] = (*this)[r][c] + matrix[r][c]; } } return ret; } void operator += (Matrix& matrix) { for(int r = 0; r < matrix.getR(); r++) { for(int c = 0; c < matrix.getC(); c++) { (*this)[r][c] += matrix[r][c]; } } } Matrix operator * (Matrix& matrix) { Matrix ret(this->getR(), matrix.getC()); for(int r = 0; r < getR(); r++) { for(int c = 0; c < matrix.getC(); c++) { for(int rr = 0; rr < matrix.getR(); rr++) { ret[r][c] += (*this)[r][rr] * matrix[rr][c]; } } } return ret; } void operator *= (Matrix& matrix) { (*this) = (*this) * matrix; } private: vector> mat; }; const int MAX_R = 10; const int MAX_C = 10; int R,C,T; int Sy,Sx; int Gy,Gx; char B[MAX_R][MAX_C]; int dr[] = {1,-1,0,0}; int dc[] = {0,0,1,-1}; signed main() { cin >> R >> C >> T; cin >> Sy >> Sx; cin >> Gy >> Gx; REP(r,R) { REP(c,C) { cin >> B[r][c]; } } Matrix startMat(1,R*C); startMat[0][Sy*C + Sx] = 1.0; Matrix moveMatrix(R*C, R*C); REP(r,R) { REP(c,C) { if(B[r][c] == '#') { continue; } double k = 0; REP(d,4) { int nr = r + dr[d]; int nc = c + dc[d]; if(B[nr][nc] != '#') { k++; } } if(k != 0) { REP(d,4) { int nr = r + dr[d]; int nc = c + dc[d]; if(B[nr][nc] != '#') { moveMatrix[r*C+c][nr*C+nc] = 1.0/k; } } } else { moveMatrix[r*C+c][r*C+c] = 1.0; } } } Matrix tmpMatrix(R*C, R*C); tmpMatrix = moveMatrix; while(T) { if(T&1) { startMat *= tmpMatrix; } T >>= 1; tmpMatrix *= tmpMatrix; } printf("%.15Lf\n", startMat[0][Gy*C+Gx]); return 0; }