結果

問題 No.367 ナイトの転身
ユーザー pekempeypekempey
提出日時 2016-08-04 18:56:19
言語 Haskell
(9.8.2)
結果
AC  
実行時間 1,914 ms / 2,000 ms
コード長 1,727 bytes
コンパイル時間 3,302 ms
コンパイル使用メモリ 190,888 KB
実行使用メモリ 90,028 KB
最終ジャッジ日時 2023-09-12 01:08:31
合計ジャッジ時間 8,694 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,652 KB
testcase_01 AC 3 ms
7,532 KB
testcase_02 AC 3 ms
7,616 KB
testcase_03 AC 3 ms
7,600 KB
testcase_04 AC 3 ms
7,724 KB
testcase_05 AC 3 ms
7,388 KB
testcase_06 AC 3 ms
7,620 KB
testcase_07 AC 3 ms
7,504 KB
testcase_08 AC 2 ms
7,684 KB
testcase_09 AC 3 ms
7,656 KB
testcase_10 AC 903 ms
47,060 KB
testcase_11 AC 1,914 ms
90,028 KB
testcase_12 AC 82 ms
15,228 KB
testcase_13 AC 122 ms
17,080 KB
testcase_14 AC 343 ms
22,488 KB
testcase_15 AC 12 ms
11,892 KB
testcase_16 AC 342 ms
22,364 KB
testcase_17 AC 53 ms
14,236 KB
testcase_18 AC 72 ms
14,624 KB
testcase_19 AC 62 ms
14,560 KB
testcase_20 AC 22 ms
12,180 KB
testcase_21 AC 63 ms
14,408 KB
testcase_22 AC 3 ms
8,128 KB
testcase_23 AC 5 ms
9,204 KB
testcase_24 AC 13 ms
12,004 KB
testcase_25 AC 12 ms
11,684 KB
testcase_26 AC 4 ms
8,848 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 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 
    | Data.Sequence.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
                    [(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, 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