Facebook Hacker Cup Round1 C

gistfile1.hs

import Control.Monad
import Control.Monad.ST
import Control.Applicative
import Text.Printf
import Data.Vector.Generic ((!))
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U

main :: IO ()
main = do
  cases <- readLn
  forM_ [1..cases::Int] $ \cn -> do
    [h, w] <- map read . words <$> getLine

    bd <- V.fromList . map U.fromList <$> replicateM h getLine

    let tbl =
          V.generate (h+2) $ \y ->
          V.generate (w+2) $ \x ->
          V.generate 6 $ \t ->
          f x y t

        f x y t
          | not $ x > 0 && x <= w && y > 0 && y <= h = 0 :: Int
          | bd ! (y-1) ! (x-1) == '#' = 0
          | t == 0 || t == 1 = 1 + max normal using
          | t == 2 || t == 3 = 1 + max using used
          | otherwise = 1 + normal
          where
            normal = max (tbl!(y+1)!x!(t`div`4*4)) (tbl!y!(x+1)!(t`div`4*4+1))
            using = (tbl!(y+dy)!(x+dx)!(t`mod`2+2))
            used = (tbl!(y+ey)!(x+ex)!4)

            (dx, dy) = if even t then (-1, 0) else (0, -1)
            (ex, ey) = if even t then (0, 1) else (1, 0)

    printf "Case #%d: %d\n" cn (tbl!1!1!0)