結果

問題 No.659 徘徊迷路
ユーザー pekempey
提出日時 2018-03-03 00:24:05
言語 Haskell
(9.10.1)
結果
WA  
実行時間 -
コード長 1,462 bytes
コンパイル時間 11,903 ms
コンパイル使用メモリ 194,176 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2024-06-23 01:14:59
合計ジャッジ時間 10,730 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 WA * 1
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

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 < 100000 = x
  | odd x = 100001
  | otherwise = 100000
0