Submission #172055

---

Source Code Expand

module Main where

import Control.Applicative
import Control.Monad
import Data.Map (Map)
import Data.Maybe
import qualified Data.Map as M

type Matrix = Map (Row, Col) Int
type Row = Int
type Col = Int

type Memo = Map (Row, Col, Int) Int

convMatrix :: [[Int]] -> Row -> [((Row, Col), Int)]
convMatrix [] _ = []
convMatrix (xs:xss) r = zip [(r, c) | c <- [0..]] xs ++ convMatrix xss (r + 1)

main :: IO ()
main = do
    [r, c, d] <- map read . words <$> getLine
    matrix <- replicateM r $ do
        map read . words <$> getLine
    let matrix' = M.fromList $ convMatrix matrix 0
    print $ solve matrix' (r, c) (0, 0) d

solve :: Matrix -> (Row, Col) -> (Row, Col) -> Int -> Int
solve mat _ (r, c) 0 = fromJust $ M.lookup (r, c) mat
solve mat (mr, mc) (r, c) d = maximum
    $ map (\cell -> solve mat (mr, mc) cell (d - 1))
    $ filter inMatrix [(r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)]
  where
    inMatrix (r', c')
        | 0 <= r' && r' < mr && 0 <= c' && c' < mc = True
        | otherwise = False

Submission Info

Judge Result