結果

問題 No.659 徘徊迷路
ユーザー pekempeypekempey
提出日時 2018-03-03 00:24:05
言語 Haskell
(9.8.2)
結果
WA  
実行時間 -
コード長 1,462 bytes
コンパイル時間 2,200 ms
コンパイル使用メモリ 184,112 KB
実行使用メモリ 11,884 KB
最終ジャッジ日時 2023-09-05 04:39:29
合計ジャッジ時間 9,619 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,688 KB
testcase_01 AC 6 ms
10,220 KB
testcase_02 AC 52 ms
11,836 KB
testcase_03 WA -
testcase_04 AC 513 ms
11,740 KB
testcase_05 AC 3 ms
7,732 KB
testcase_06 AC 3 ms
7,852 KB
testcase_07 AC 3 ms
7,696 KB
testcase_08 AC 22 ms
11,764 KB
testcase_09 AC 762 ms
11,844 KB
testcase_10 AC 852 ms
11,756 KB
testcase_11 AC 832 ms
11,884 KB
testcase_12 AC 3 ms
8,252 KB
testcase_13 AC 823 ms
11,864 KB
testcase_14 AC 822 ms
11,840 KB
testcase_15 AC 822 ms
11,792 KB
testcase_16 AC 813 ms
11,796 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/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