• + 0 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