using System; using System.IO; using System.Collections.Generic; namespace No659_3 { public class Program { void Solve(StreamScanner ss, StreamWriter sw) { //--------------------------------- var H = ss.Next(Int); var W = ss.Next(Int); var T = ss.Next(Int); var Sy = ss.Next(Int); var Sx = ss.Next(Int); var Gy = ss.Next(Int); var Gx = ss.Next(Int); var B = ss.Next(String, H); var d = new (int x, int y)[] {(0, 1), (1, 0), (0, -1), (-1, 0)}; var canGo = new List<(int x, int y)>[H, W]; for (var y = 1; y < H - 1; y++) { for (var x = 1; x < W - 1; x++) { if (B[y][x] == '#') continue; canGo[y, x] = new List<(int x, int y)>(); for (var i = 0; i < d.Length; i++) { var nx = x + d[i].x; var ny = y + d[i].y; if (B[ny][nx] == '.') canGo[y, x].Add((nx, ny)); } } } var walkCount = Math.Min(T, 4000 + T % 2); var dp = new double[2][,]; dp[0] = new double[H, W]; dp[0][Sy, Sx] = 1.0; for (var k = 1; k <= walkCount; k++) { dp[k % 2] = new double[H, W]; for (var y = 1; y < H - 1; y++) { for (var x = 1; x < W - 1; x++) { if (B[y][x] == '#') continue; if (canGo[y,x].Count == 0) { dp[k % 2][y, x] = dp[(k - 1) % 2][y, x]; continue; } foreach (var (nx, ny) in canGo[y,x]) { dp[k % 2][ny, nx] += dp[(k - 1) % 2][y, x] / canGo[y, x].Count; } } } } sw.WriteLine(dp[walkCount % 2][Gy, Gx]); //--------------------------------- } static void Main() { var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput())); var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; new Program().Solve(ss, sw); sw.Flush(); } static readonly Func String = s => s; static readonly Func Int = int.Parse; static readonly Func Long = long.Parse; static readonly Func Double = double.Parse; } public class StreamScanner { static readonly char[] Sep = { ' ' }; readonly Queue buffer = new Queue(); readonly TextReader textReader; public StreamScanner(TextReader textReader) { this.textReader = textReader; } public T Next(Func parser) { if (buffer.Count != 0) return parser(buffer.Dequeue()); var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries); foreach (var nextString in nextStrings) buffer.Enqueue(nextString); return Next(parser); } public T[] Next(Func parser, int x) { var ret = new T[x]; for (var i = 0; i < x; ++i) ret[i] = Next(parser); return ret; } public T[][] Next(Func parser, int x, int y) { var ret = new T[y][]; for (var i = 0; i < y; ++i) ret[i] = Next(parser, x); return ret; } } }