import std.stdio; import std.range; import std.array; import std.string; import std.conv; import std.typecons; import std.algorithm; import std.container; import std.typecons; import std.random; import core.time; void main() { auto f = readln.chomp.split.map!(to!int); int r, c, t; r = f[0]; c = f[1]; t = f[2]; int[] s = readln.chomp.split.map!(to!int).retro.array; int[] g = readln.chomp.split.map!(to!int).retro.array; double[][][] prob = new double[][][](2, r, c); string[] field; foreach (y; 0..r) { field ~= readln.chomp; } bool reached = false; bool[string[]] set; foreach (ref v; prob[0]) { v []= 0.0; } prob[0][s[1]][s[0]] = 1; foreach (i; 0..min(t, 100000)) { foreach (y; 0..r) { prob[1 - i % 2][y] []= 0.0; } foreach (y; 0..r) { foreach (x; 0..c) { if (field[y][x] == '#') { continue; } int p = 0; enum OFS = [ [0, 1], [1, 0], [-1, 0], [0, -1] ]; foreach (D; OFS) { auto nx = x + D[0]; auto ny = y + D[1]; if (field[ny][nx] == '#') { continue; } ++p; } foreach (D; OFS) { auto nx = x + D[0]; auto ny = y + D[1]; if (field[ny][nx] == '#') { continue; } prob[1 - i % 2][ny][nx] += (1.0 / p) * prob[i % 2][y][x]; } } } reached |= prob[1 - i % 2][g[1]][g[0]] > 0; if (reached) { auto arr = [format("%.7f", prob[i % 2][g[1]][g[0]]), format("%.7f", prob[1 - i % 2][g[1]][g[0]])]; if (arr in set) { arr[0].writeln; return; } set[arr.idup] = true; } } format("%.7f", prob[t % 2][g[1]][g[0]]).writeln; }