結果

問題 No.13 囲みたい！
コンテスト
ユーザー aimy
提出日時 2017-05-12 10:38:18
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,150 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 149,632 KB
最終ジャッジ日時 2024-11-15 04:45:39
合計ジャッジ時間 642 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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:3:1: error: [GHC-87110]
    Could not load module ‘Data.IntMap’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
  |
3 | import qualified Data.IntMap as M
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:4:1: error: [GHC-87110]
    Could not load module ‘Data.IntSet’.
    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.IntSet as S
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

import Data.Bool
import Data.List
import qualified Data.IntMap as M
import qualified Data.IntSet as S

unionMap f s = S.foldr (\e acc -> S.union acc (f e)) S.empty s

main = do
 [w,h] <- map read . words <$> getLine
 ms <- map read . words <$> getContents :: IO [Int]
 putStrLn (bool "impossible" "possible" (anyClosed w h ms))

anyClosed w h ms = or (unfoldr (dfs w) ims)
 where ims = M.fromDistinctAscList (zip [i | i<-[1..(w+1)*h], mod i (w+1) /= 0] ms)

dfs w ims
 | M.null ims = Nothing
 | otherwise = Just (isClosed w [i,i] (M.keysSet ims'), M.difference ims ims')
 where
  (i,m) = head (M.toList ims)
  ims' = reachable w m ims (S.singleton i) (S.singleton i)

reachable w m ims acc b
 | S.null b = M.filterWithKey (\k _ -> S.member k acc) ims
 | otherwise = reachable w m ims (S.union acc b') (S.difference b' acc)
  where
   b' = unionMap (\i -> S.fromList (filter movable [i-1,i+1,i-(w+1),i+(w+1)])) b
   movable k = M.findWithDefault 0 k ims == m

isClosed w acc@(a:a':as) is
 | S.null is = False
 | not (S.member a is) = False
 | elem a as = True
 | otherwise = or (map (\i -> isClosed w (i:acc) is) (delete a' [a-1,a+1,a-(w+1),a+(w+1)]))
0