// 基本テンプレート #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define debug(...) fprintf(stderr, __VA_ARGS__) #define int long long int template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} typedef pair pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 1000000007LL; // 行列ライブラリ // Verified: TopCoder SRM 704 Div.2 (ModEquationEasy) // 行列の積 と 累乗(繰り返し二乗法) // Matrix Library Begin (C++11) template using Matrix = vector< vector >; template void init_mat(Matrix &A, int h, int w) { A.resize(h, vector(w, 0)); } template Matrix calc_mat(Matrix A, Matrix B) { Matrix C(A.size(), vector(B[0].size())); for(int i=0; i Matrix mat_pow(Matrix A, ll n) { Matrix B(A.size(), vector(A.size())); for(int i=0; i 0) { if(n & 1) B = calc_mat(B, A); A = calc_mat(A, A); n >>= 1; } return B; } // Matrix Library End int R, C, T; int get_idx(int x, int y) { return C*x + y; } char board[15][15]; signed main() { cin >> R >> C >> T; int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy; for(int i=0; i> board[i][j]; } } Matrix mat; init_mat(mat, R*C, R*C); for(int i=0; i= R || ny < 0 || ny >= C) continue; if(board[nx][ny] == '#') continue; cnt++; } for(int k=0; k<4; k++) { int nx = i + dx[k], ny = j + dy[k]; if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue; if(board[nx][ny] == '#') continue; int i1 = get_idx(i, j), i2 = get_idx(nx, ny); mat[i2][i1] += 1.0 / cnt; } if(cnt == 0) { int idx = get_idx(i, j); mat[idx][idx] += 1; } } } Matrix vec; init_mat(vec, R*C, 1); vec[get_idx(sx, sy)][0] = 1.0; mat = calc_mat(mat_pow(mat, T), vec); printf("%.12f\n", mat[get_idx(gx, gy)][0]); return 0; }