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; } alias Point = Tuple!(int, "x", int, "y"); bool[Point] done; Point[] queue; queue ~= Point(s[0], s[1]); enum OFS = [ [0, 1], [1, 0], [-1, 0], [0, -1] ]; while (queue.length) { Point node = queue[0]; queue = queue[1..$]; if (node in done) { continue; } done[node] = true; foreach (D; OFS) { Point next = Point(node.x + D[0], node.y + D[1]); if (field[next.y][next.x] == '#') { continue; } queue ~= next; } } if (Point(g[0], g[1]) !in done) { 0.writeln; return; } bool reached = false; bool[string[]] set; foreach (ref v; prob[0]) { v []= 0.0; } prob[0][s[1]][s[0]] = 1; foreach (i; 0..t) { 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; 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]; } if (p == 0) { prob[1 - i % 2][y][x] = prob[i % 2][y][x]; } } } reached |= format("%.7f", prob[1 - i % 2][g[1]][g[0]]) != "0.0000000"; 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; }