# Sherlock and the Maze

# Sherlock and the Maze

+ 0 comments DP with Memoization in Haskell

import Data.Array (Ix, array, bounds, inRange, (!)) import Prelude hiding (Right) data Direction = Neutral | Down | Right deriving (Eq, Ord, Ix) paths :: Int -> Int -> Int -> Integer paths m n k = go (1, 1, k, Neutral) where go (i, j, k, dir) | i == m && j == n = 1 | otherwise = case dir of Neutral -> mod (get (i+1, j, k, Down) + get (i, j+1, k, Right)) (10^9 + 7) Down -> mod (get (i+1, j, k, Down) + get (i, j+1, k-1, Right)) (10^9 + 7) Right -> mod (get (i+1, j, k-1, Down) + get (i, j+1, k, Right)) (10^9 + 7) a = array ((1, 1, 0, Down), (m, n, k, Right)) [(c, go c) | c <- (,,,) <$> [1..m] <*> [1..n] <*> [0..k] <*> [Down, Right]] get x | inRange (bounds a) x = a ! x | otherwise = 0 helper :: [String] -> Integer helper arr = do let new = map (read :: String -> Int) arr paths (new!!0) (new!!1) (new!!2) main :: IO() main = do raw <- getContents mapM_ print $ map helper $ tail $ map words $ lines raw

+ 0 comments **He is free to face any direction before starting from (1, 1).**If he faces downwards direction but choose to move rightwards then he can reach(2,2) with 2 turns which contradicts the test case # 1. ?

+ 1 comment What is the timeout for test case #5, i have verified the answer its correct and runs around 3 seconds on my laptop, it still timesout here

+ 3 comments isn't this chalenge more about finding the good mathematic formula than a real programming chalenge ? :/

+ 0 comments Input : for 2nd test case 2 3 1 you can not reach to 2,3 with 1 turn. please explain

what ever the test case explanation is incorrect Test Case #01: He can't reach (2, 3) with 0 turns. There are only two ways to reach (2, 3) with exactly 1 turn. 1.He starts from (1, 1) facing down and moves to (2, 1). Then he turns right and takes two steps forward to reach (2, 3). 2.He starts from (1, 1) facing right and moves two steps forward to reach (1, 3). Then he turns down and proceeds one step to (2, 3).

Sort 7 Discussions, By:

Please Login in order to post a comment