using System; using System.IO; using System.Collections.Generic; namespace No659_2 { 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); int[] dx = { 0, 1, 0, -1 }; int[] dy = { 1, 0, -1, 0 }; var dl = 4; var walkCount = Math.Min(T, 4000 + T % 2); var dp = new double[walkCount + 1, H, W]; dp[0, Sy, Sx] = 1.0; for (var k = 1; k <= walkCount; k++) { for (var y = 1; y < H - 1; y++) { for (var x = 1; x < W - 1; x++) { if (B[y][x] == '#') continue; var xQue = new Queue(); var yQue = new Queue(); var qc = 0; for (var i = 0; i < dl; i++) { var nx = x + dx[i]; var ny = y + dy[i]; if (B[ny][nx] == '.') { xQue.Enqueue(nx); yQue.Enqueue(ny); qc++; } } if (qc == 0) dp[k, y, x] = dp[k - 1, y, x]; while (xQue.Count > 0) { var nx = xQue.Dequeue(); var ny = yQue.Dequeue(); dp[k, ny, nx] += dp[k - 1, y, x] / qc; } } } } sw.WriteLine(dp[walkCount, 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; } } }