2b.hs

import Data.List
import Data.Maybe (maybeToList)
import Data.Functor ((<$>))
import Data.Function (on)
import Control.Monad (when)
import qualified Data.Array.Unboxed as U
import qualified Data.Array.ST as ST
import qualified Data.ByteString.Char8 as B hiding (minimum)

getPows :: Int -> Int -> Int
getPows b x = case x `divMod` b of
                 (x', 0) -> 1 + getPows b x'
                 _ -> 0

solve :: Int -> U.UArray (Int, Int) Int -> Int -> (Int, String)
solve n mat b = (dp U.! (0, 0), findPath 0 0)
  where dp = ST.runSTUArray $ do
          let thunk = -1
          dp' <- ST.thaw (U.listArray ((0, 0), (n, n)) (repeat thunk) :: U.UArray (Int, Int) Int)

          let f i j = do
                tmp <- ST.readArray dp' (i, j)
                when (tmp == thunk) $ ST.writeArray dp' (i, j) =<< f' i j
                ST.readArray dp' (i, j)

              f' i j
                | i == n-1 && j == n-1 = return gridWeight
                | i == n-1 = rpath
                | j == n-1 = dpath
                | otherwise = minimum <$> sequence [dpath, rpath]
                where gridWeight = getPows b $ mat U.! (i, j)
                      dpath = (gridWeight + ) <$> f (i+1) j
                      rpath = (gridWeight + ) <$> f i (j+1)

          ST.writeArray dp' (0, 0) =<< f 0 0
          return dp'

        findPath i j
          | i == n-1 = replicate (n-j-1) 'R'
          | j == n-1 = replicate (n-i-1) 'D'
          | otherwise =
            if dp U.! (i, j+1) > dp U.! (i+1, j)
            then 'D' : findPath (i+1) j
            else 'R' : findPath i (j+1)

readInt :: B.ByteString -> Int
readInt = maybe 0 fst . B.readInt

main :: IO ()
main = do
  n : mat' <- map readInt . B.words <$> B.getContents
  let zeroPath idx = (1, replicate x 'R' ++ replicate (n-1) 'D' ++ replicate (n-1-x) 'R')
        where x = idx `mod` n
      maybeZeroPath = maybeToList $ zeroPath <$> elemIndex 0 mat'
      mat = U.listArray ((0, 0), (n-1, n-1)) (map (\x -> if x == 0 then 10 else x) mat')

  let cands = maybeZeroPath ++ map (solve n mat) [2, 5]
      (ansWeight, ansPath) = minimumBy (compare `on` fst) cands

  print ansWeight
  putStrLn ansPath