import Data.Array import Data.Array.IO import Control.Monad import Text.Printf addTo :: IOUArray Int Double -> Int -> Double -> IO () addTo a k x = do v <- readArray a k writeArray a k (v + x) main = do [h, w, t] <- map read . words <$> getLine :: IO [Int] [sy, sx] <- map read . words <$> getLine :: IO [Int] [gy, gx] <- map read . words <$> getLine :: IO [Int] g <- listArray (0, h - 1) . map (listArray (0, w - 1)) <$> replicateM h getLine :: IO (Array Int (Array Int Char)) let tt = f t dp0 <- newArray (0, h * w - 1) 0 :: IO (IOUArray Int Double) dp1 <- newArray (0, h * w - 1) 0 :: IO (IOUArray Int Double) writeArray dp0 (sy * w + sx) 1.0 forM_ [1..tt] $ \_ -> do forM_ [0..h * w - 1] $ \i -> writeArray dp1 i 0 forM_ [1..h - 2] $ \i -> do forM_ [1..w - 2] $ \j -> do let ij = i * w + j let adj = [(ni, nj) | (di, dj) <- [(1, 0), (-1, 0), (0, 1), (0, -1)], let ni = i + di, let nj = j + dj, g!ni!nj == '.'] let cnt = length adj if cnt > 0 then do let p = 1.0 / (fromIntegral cnt) :: Double forM_ adj $ \(ny, nx) -> (* p) <$> readArray dp0 ij >>= addTo dp1 (ny * w + nx) else forM_ adj $ \(ny, nx) -> readArray dp0 ij >>= addTo dp1 ij forM_ [0..h * w - 1] $ \i -> readArray dp1 i >>= writeArray dp0 i readArray dp0 (gy * w + gx) >>= printf "%.20f\n" f :: Int -> Int f x | x < 50000 = x | odd x = 50001 | otherwise = 50000