Submission #69698994


Source Code Expand

import Data.Char
import Data.List
import Data.Maybe

import Control.Monad
import Control.Monad.ST
import Data.Array.IArray
import Data.Array.MArray
import Data.Array.ST -- STUArray で使用
import Debug.Trace

import Data.Array.Unboxed qualified as AU
import Data.ByteString.Char8 qualified as BS

readInts :: IO [Int]
readInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

{-
 - 最初に候補を全て選んでまとめて処理
 - 次のレベルに移るときに候補でなくなったものがあるので候補を作り直して進む
 -}

main :: IO ()
main = do
  [h,w] <- readInts
  ss <- replicateM h getLine
  let g = AU.listArray ((1,1),(h,w)) $ concat ss :: AU.UArray (Int,Int) Char
  let cands = solve g
  let ans = filter id $ AU.elems cands
  print $ length ans

solve :: AU.UArray (Int,Int) Char -> AU.UArray (Int,Int) Bool
solve g = runSTUArray $ do
  -- 未訪問(-1)を設定する
  arr <- newArray ((1,1),(h,w)) False :: ST s (STUArray s (Int,Int) Bool)
  let starts = [(i,j)| i <- [1..h], j <- [1..w], g AU.! (i,j) == '#']
  bfs arr starts []
  return arr
  where
    (_,(h,w)) = AU.bounds g
    -- bfs
    -- arr :: 訪問済みリスト
    -- vs :: 現在同じ距離に属する節点リスト
    -- us :: 次の距離に属する節点リスト
    bfs arr [] [] = return () -- 候補がなくなった(終了)
    bfs arr [] us = do -- usの候補を精査する
      let fDir (i,j) = filter (AU.inRange ((1,1),(h,w))) [(i+1,j),(i-1,j),(i,j+1),(i,j-1)] -- 4方向で範囲内のものを取り出す
      cands <- forM us $ \neighbor -> do -- その先の接続先を確認
        let neighbors2 = fDir neighbor
        neighbors3 <- filterM (\(i,j) -> readArray arr (i,j)) neighbors2 -- 訪問済みの個数を数える
        if length neighbors3 == 1 then
          return (Just neighbor)
        else
          return Nothing
      let neighborsFinal = catMaybes cands
      bfs arr neighborsFinal [] -- 次のグループへ
    bfs arr (v:vs) us = do -- メインの処理
      writeArray arr v True
      let fDir (i,j) = filter (AU.inRange ((1,1),(h,w))) [(i+1,j),(i-1,j),(i,j+1),(i,j-1)] -- 4方向で範囲内のものを取り出す
      let dir4 = fDir v
      neighbors1 <- filterM (\(i,j) -> not <$> readArray arr (i,j)) dir4 -- 訪問済みでないこと
      bfs arr vs (neighbors1 ++ us)

Submission Info

Submission Time
Task D - Ulam-Warburton Automaton
User haskboy
Language Haskell (GHC 9.4.5)
Score 425
Code Size 2426 Byte
Status AC
Exec Time 275 ms
Memory 137688 KiB

Compile Error

app/Main.hs:7:1: warning: [-Wunused-imports]
    The import of ‘Data.Array.IArray’ is redundant
      except perhaps to import instances from ‘Data.Array.IArray’
    To import instances alone, use: import Data.Array.IArray()
  |
7 | import Data.Array.IArray
  | ^^^^^^^^^^^^^^^^^^^^^^^^

app/Main.hs:10:1: warning: [-Wunused-imports]
    The import of ‘Debug.Trace’ is redundant
      except perhaps to import instances from ‘Debug.Trace’
    To import instances alone, use: import Debug.Trace()
   |
10 | import Debug.Trace
   | ^^^^^^^^^^^^^^^^^^

app/Main.hs:45:9: warning: [-Wunused-matches]
    Defined but not used: ‘arr’
   |
45 |     bfs arr [] [] = return () -- 候補がなくなった(終了)
   |         ^^^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 40
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 2 ms 7104 KiB
00_sample_01.txt AC 2 ms 6812 KiB
00_sample_02.txt AC 1 ms 7168 KiB
01_test_00.txt AC 192 ms 66220 KiB
01_test_01.txt AC 82 ms 47568 KiB
01_test_02.txt AC 92 ms 51820 KiB
01_test_03.txt AC 152 ms 60004 KiB
01_test_04.txt AC 172 ms 59116 KiB
01_test_05.txt AC 275 ms 132780 KiB
01_test_06.txt AC 274 ms 126632 KiB
01_test_07.txt AC 275 ms 137688 KiB
01_test_08.txt AC 233 ms 75428 KiB
01_test_09.txt AC 253 ms 81532 KiB
01_test_10.txt AC 92 ms 26504 KiB
01_test_11.txt AC 112 ms 27320 KiB
01_test_12.txt AC 122 ms 27868 KiB
01_test_13.txt AC 122 ms 28284 KiB
01_test_14.txt AC 142 ms 26900 KiB
01_test_15.txt AC 152 ms 28392 KiB
01_test_16.txt AC 172 ms 29144 KiB
01_test_17.txt AC 192 ms 37344 KiB
01_test_18.txt AC 212 ms 42692 KiB
01_test_19.txt AC 223 ms 49768 KiB
01_test_20.txt AC 71 ms 24396 KiB
01_test_21.txt AC 71 ms 25416 KiB
01_test_22.txt AC 71 ms 24420 KiB
01_test_23.txt AC 81 ms 24420 KiB
01_test_24.txt AC 81 ms 25416 KiB
01_test_25.txt AC 91 ms 25444 KiB
01_test_26.txt AC 101 ms 24800 KiB
01_test_27.txt AC 131 ms 24456 KiB
01_test_28.txt AC 92 ms 30540 KiB
01_test_29.txt AC 102 ms 40300 KiB
01_test_30.txt AC 102 ms 30736 KiB
01_test_31.txt AC 91 ms 30680 KiB
01_test_32.txt AC 101 ms 30984 KiB
01_test_33.txt AC 112 ms 31568 KiB
01_test_34.txt AC 132 ms 32032 KiB
01_test_35.txt AC 162 ms 32992 KiB
01_test_36.txt AC 72 ms 25336 KiB