Sort 7 Discussions, By:
Please Login in order to post a comment
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
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. ?
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
isn't this chalenge more about finding the good mathematic formula than a real programming chalenge ? :/
Input : for 2nd test case
2 3 1
you can not reach to 2,3 with 1 turn.
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).