You are viewing a single comment's thread. Return to all comments →
Haskell
module Main where import Control.Monad (replicateM) import qualified Data.Map as M import qualified Data.Set as S type Center = (Int, Int) type Radius = Int type Plus = (Center, Radius) goodcoords :: [[Bool]] -> S.Set Center goodcoords = S.fromList . concat . zipWith (\i -> map (\(j, b) -> (i, j)) . filter snd . zip [0 ..]) [0 ..] allplusses :: S.Set Center -> [Plus] allplusses good = concatMap plusseshere goodList where goodList = S.toList good plusseshere :: Center -> [Plus] plusseshere c = go 0 where go r = if all (\(dx, dy) -> S.member (fst c + dx, snd c + dy) good) [(0, r), (0, -r), (r, 0), (-r, 0)] then (c, r) : go (r + 1) else [] plusintersect :: Plus -> Plus -> Bool plusintersect ((x1, y1), s1) ((x2, y2), s2) = do let set1 = S.fromList [(x1 + dx, y1 + dy) | (dx, dy) <- [(0, r) | r <- [-s1 .. s1]] ++ [(r, 0) | r <- [-s1 .. s1]]] set2 = S.fromList [(x2 + dx, y2 + dy) | (dx, dy) <- [(0, r) | r <- [-s2 .. s2]] ++ [(r, 0) | r <- [-s2 .. s2]]] not $ S.null $ S.intersection set1 set2 runmax :: [Plus] -> Int runmax ps = go ps 0 where go :: [Plus] -> Int -> Int go [] m = m go (p@(_, pr) : ps) m = do let qrs = [qr | q@(_, qr) <- ps, not (plusintersect p q)] case qrs of [] -> go ps m _ -> go ps (max m ((4 * pr + 1) * (4 * maximum qrs + 1))) solve :: [[Bool]] -> Int solve = runmax . allplusses . goodcoords main :: IO () main = do [n, m] <- map read . words <$> getLine :: IO [Int] grid <- replicateM n $ do map (== 'G') <$> getLine print $ solve grid
Seems like cookies are disabled on this browser, please enable them to open this website
Ema's Supercomputer
You are viewing a single comment's thread. Return to all comments →
Haskell