#include #include #include int R, C, T; int Sy, Sx, Gy, Gx; double dp[10][10] = {0}, next_dp[10][10] = {0}; char Board[10][11]; long flags[10][10] = {0}; const int DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; const int BITS_COUNT[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, }; int main(void) { scanf("%d %d %d\n", &R, &C, &T); scanf("%d %d\n", &Sy, &Sx); scanf("%d %d\n", &Gy, &Gx); for (int y = 0; y < R; ++y) { scanf("%s\n", Board[y]); } for (int y = 1; y < R-1; ++y) { for (int x = 1; x < C-1; ++x) { long flg = 0; for (int d = 0; d < 4; ++d) { int dy = DIRS[d][0]; int dx = DIRS[d][1]; if (Board[y+dy][x+dx] == '#') continue; flg |= 1 << d; } flags[y][x] = flg; } } dp[Sy][Sx] = 1.0; int times = T > 5000 ? (5000 | T%2) : T; for (int i = 0; i < times; ++i) { for (int y = 1; y < R-1; ++y) { for (int x = 1; x < C-1; ++x) { if (Board[y][x] == '#') continue; int dir_count = BITS_COUNT[flags[y][x]]; if (dir_count == 0) { next_dp[y][x] += dp[y][x]; continue; } for (int d = 0; d < 4; ++d) { if (flags[y][x] & (1 << d) == 0) continue; int dy = DIRS[d][0]; int dx = DIRS[d][1]; next_dp[y+dy][x+dx] += dp[y][x] / (double)dir_count; } } } memcpy(dp, next_dp, sizeof(next_dp)); memset(next_dp, 0, sizeof(next_dp)); // for (int i = 0; i < 10; ++i) { // for (int j = 0; j < 10; ++j) { // printf("%f ", dp[i][j]); // // printf("%d ", flags[i][j]); // } // puts(""); // } } printf("%f\n", dp[Gy][Gx]); }