結果

問題 No.659 徘徊迷路
ユーザー pekempeypekempey
提出日時 2018-03-03 00:24:05
言語 Haskell
(9.8.2)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 5 ms
6,944 KB
testcase_02 AC 50 ms
8,320 KB
testcase_03 WA -
testcase_04 AC 453 ms
8,064 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 11 ms
8,192 KB
testcase_09 AC 672 ms
8,320 KB
testcase_10 AC 752 ms
8,320 KB
testcase_11 AC 738 ms
8,320 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 723 ms
8,320 KB
testcase_14 AC 725 ms
8,064 KB
testcase_15 AC 733 ms
8,192 KB
testcase_16 AC 796 ms
8,320 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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