#include #include #include #include #include #include using namespace std; #define MAX 1000001 typedef vector vec; typedef vector mat; char map[10][10]; int r, c, t, sx, sy, gx, gy; int ds[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; mat mul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); for(int i=0; i0) { if(n&1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } // memo aがおかしい double solve() { { int unko = 0; for(int k=0; k<4; k++) { int ny = sy+ds[k][0]; int nx = sx+ds[k][1]; if(0<=ny && ny < r && 0<=nx && nx < c && map[ny][nx] == '.') unko++; } //printf("unko=%d, sx=%d, gx=%d, sy=%d, gy=%d\n", unko, sx, gx, sy, gy); // if(unko==0 && sx==gx && sy==gy) return 1; if(unko==0) return 0; } mat A(101, vec(101)); for(int y=0; y (%d, %d) = %f\n", y, x, ny, nx, (double)1/(double)tmp); if(tmp==0) break; A[current][next] = (double)1/(double)tmp; //assert(A[current][next]<=1.0); //printf("A[c][n]=%f\n", A[current][next]); } } //printf("@@@@@\n"); } //if(y==0) printMat(A); } } // A = pow(A, t); // for(int y=0; y (%d, %d) = %f\n", y, x, ny, nx, A[current][next]); // } // } // } // } //printMat(A); A = pow(A, t); return A[c*sy+sx][c*gy+gx]; } int main() { cin >> r >> c >> t >> sy >> sx >> gy >> gx; for(int i=0; i