結果

問題 No.367 ナイトの転身
ユーザー pekempeypekempey
提出日時 2016-08-04 19:53:14
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,182 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 149,888 KB
最終ジャッジ日時 2024-11-14 19:48:08
合計ジャッジ時間 491 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:4:1: error: [GHC-87110]
    Could not load module ‘Data.Sequence’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
  |
4 | import qualified Data.Sequence
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:5:1: error: [GHC-87110]
    Could not load module ‘Data.Set’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
  |
5 | import qualified Data.Set
  | ^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:8:1: error: [GHC-87110]
    Could not load module ‘Data.Time’.
    It is a member of the hidden package ‘time-1.12.2’.
    Use -v to see a list of the files searched for.
  |
8 | import Data.Time
  | ^^^^^^^^^^^^^^^^

ソースコード

diff # 

import Control.Applicative
import Data.List
import Data.Array.Unboxed
import qualified Data.Sequence
import qualified Data.Set
import Data.Maybe
import Debug.Trace
import Data.Time

-- 2-stack queue
-- partial persistent として使うのであれば各操作 amortized O(1)
data Queue a = Node [a] [a]

queueEmpty = Node [] []

queueNull (Node [] []) = True
queueNull (Node _ _) = False

enqueue x (Node s1 s2) = Node s1 (x : s2)

dequeue (Node [] s2) = dequeue (Node (reverse s2) [])
dequeue (Node (s:s1) s2) = (s, Node s1 s2)

main = do
    from <- getCurrentTime
    [h, w] <- map read . words <$> getLine :: IO [Int]
    ss <- concat . map (\(i, s) -> zip (zip (repeat i) [1..]) s) . zip [1..] . lines <$> getContents :: IO [((Int, Int), Char)]
    let grid = array ((1, 1), (h, w)) ss :: UArray (Int, Int) Char
    let (y, x) = startPoint grid
    print $ bfs grid h w (enqueue (y, x, 0, 0) queueEmpty) (Data.Set.fromList [y * w + x])
    -- to <- getCurrentTime
    -- print $ diffUTCTime to from

startPoint = fst . fromJust . find (\(i, x) -> x == 'S') . Data.Array.Unboxed.assocs

bfs :: UArray (Int, Int) Char -> Int -> Int -> Queue (Int, Int, Int, Int) -> Data.Set.Set Int -> Int
bfs grid h w q vis 
    | queueNull q          = -1
    | grid ! (y, x) == 'G' = turn
    | otherwise            = 
        let
            inside y x = 1 <= y && y <= h && 1 <= x && x <= w
            dd = if t == 0 then
                    [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
                 else
                    [(-1, -1), (-1, 1), (1, -1), (1, 1)]
            npos = [(y + dy, x + dx) | (dy, dx) <- dd, inside (y + dy) (x + dx)]
            nst = [(ny, nx, nt) | (ny, nx) <- npos, nt <- [if grid ! (ny, nx) == 'R' then 1 - t else t], Data.Set.notMember (ny * w + nx + nt * w * h) vis]
            nstate = [(ny, nx, nt, turn + 1) | (ny, nx, nt) <- nst]
            -- nvis = foldr Data.Set.insert vis nst
            nvis = Data.Set.union vis (Data.Set.fromList (map (\(y, x, t) -> y * w + x + t * w * h) nst))
            nque = foldr enqueue que nstate
        in bfs grid h w nque nvis
    where
        ((y, x, t, turn), que) = dequeue q
0