結果

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

ソースコード

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

dequeue que = case Data.Sequence.viewl que of (x Data.Sequence.:< xs) -> (x, xs)

main = do
    [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 (Data.Sequence.fromList [(y, x, 0, 0)]) (Data.Set.fromList [(y, x, 0)])

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

bfs :: UArray (Int, Int) Char -> Int -> Int -> Data.Sequence.Seq (Int, Int, Int, Int) -> Data.Set.Set (Int, Int, Int) -> Int
bfs grid h w q vis 
    | null 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
                    [(dy, dx) | dy <- [-2 .. 2], dx <- [-2 .. 2], abs dy + abs dx == 3]
                 else
                    [(dy, dx) | dy <- [-1 .. 1], dx <- [-1 .. 1], abs dy + abs dx == 2]
            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, nx, nt) vis]
            nstate = [(ny, nx, nt, turn + 1) | (ny, nx, nt) <- nst]
            nvis = foldr Data.Set.insert vis nst
            nque = foldl' (Data.Sequence.|>) que nstate
        in bfs grid h w nque nvis
    where
        ((y, x, t, turn), que) = dequeue q
0