81 lines
3.1 KiB
Haskell
81 lines
3.1 KiB
Haskell
import qualified Data.Vector.Unboxed.Mutable as V
|
|
import Data.STRef
|
|
import Control.Monad (forM_, when)
|
|
import Control.Monad.ST
|
|
|
|
dir :: [(Int, Int)]
|
|
dir = [(1, 0), (-1, 0), (0, -1), (0, 1)]
|
|
|
|
data Env = Env { w, h, len, count, ret :: !Int, next :: ![Int] }
|
|
|
|
cutIt :: STRef s Env -> ST s ()
|
|
cutIt env = do
|
|
e <- readSTRef env
|
|
when (odd $ h e) $ modifySTRef env $ \en -> en { h = w e,
|
|
w = h e }
|
|
e <- readSTRef env
|
|
if odd (h e)
|
|
then modifySTRef env $ \en -> en { ret = 0 }
|
|
else
|
|
if w e == 1
|
|
then modifySTRef env $ \en -> en { ret = 1 }
|
|
else do
|
|
let blen = (h e + 1) * (w e + 1) - 1
|
|
t = (h e `div` 2) * (w e + 1) + (w e `div` 2)
|
|
modifySTRef env $ \en -> en { len = blen,
|
|
count = 0,
|
|
next = [ w e + 1, (negate $ w e) - 1, -1, 1] }
|
|
grid <- V.replicate (blen + 1) False
|
|
case odd (w e) of
|
|
True -> do
|
|
V.write grid t True
|
|
V.write grid (t + 1) True
|
|
walk grid (h e `div` 2) (w e `div` 2 - 1)
|
|
e1 <- readSTRef env
|
|
let res1 = count e1
|
|
modifySTRef env $ \en -> en { count = 0 }
|
|
walk grid (h e `div` 2 - 1) (w e `div` 2)
|
|
modifySTRef env $ \en -> en { ret = res1 +
|
|
(count en * 2) }
|
|
False -> do
|
|
V.write grid t True
|
|
walk grid (h e `div` 2) (w e `div` 2 - 1)
|
|
e2 <- readSTRef env
|
|
let count2 = count e2
|
|
if h e == w e
|
|
then modifySTRef env $ \en -> en { ret =
|
|
count2 * 2 }
|
|
else do
|
|
walk grid (h e `div` 2 - 1)
|
|
(w e `div` 2)
|
|
modifySTRef env $ \en -> en { ret =
|
|
count en }
|
|
where
|
|
walk grid y x = do
|
|
e <- readSTRef env
|
|
if y <= 0 || y >= h e || x <= 0 || x >= w e
|
|
then modifySTRef env $ \en -> en { count = count en + 1 }
|
|
else do
|
|
let t = y * (w e + 1) + x
|
|
V.write grid t True
|
|
V.write grid (len e - t) True
|
|
forM_ (zip (next e) [0..3]) $ \(n, d) -> do
|
|
g <- V.read grid (t + n)
|
|
when (not g) $
|
|
walk grid (y + fst (dir !! d)) (x + snd (dir !! d))
|
|
V.write grid t False
|
|
V.write grid (len e - t) False
|
|
|
|
cut :: (Int, Int) -> Int
|
|
cut (x, y) = runST $ do
|
|
env <- newSTRef $ Env { w = y, h = x, len = 0, count = 0, ret = 0, next = [] }
|
|
cutIt env
|
|
result <- readSTRef env
|
|
return $ ret result
|
|
|
|
main :: IO ()
|
|
main = do
|
|
mapM_ (\(x, y) -> when (even (x * y)) (putStrLn $
|
|
show x ++ " x " ++ show y ++ ": " ++ show (cut (x, y))))
|
|
[ (x, y) | x <- [1..10], y <- [1..x] ]
|