提出 #69698994

---

ソースコード 拡げる

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)

提出情報

コンパイルエラー

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 () -- 候補がなくなった(終了)
   |         ^^^

ジャッジ結果