We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
DP gives an efficient solution to the problem (solves all test cases in 0s with C). The basic idea is as follows :
1) Calculate number of minimum moves required to reach each every square, starting from 1 till 100 (square 100 gives the answer). Initialize all the sqaures with a "very high value" to begin with.
2) Ladders : If the current square is starting-point of ladder, update the square at the end-point of the ladder (note : end-point of ladder > start-point of ladder). If the minimum moves required to reach the current square is "c" and the current value of square at the end-point of ladder is "x" then the updated value should be min(c,x).
3) Snakes : If the current square is starting-point for snake, update the square at the end-point (tail) of the snake only if the moves required to reach the current square is less than the "value of square at the tail of the snake". If the value is updated, start calculating the moves from the tail of the snake (end-point for snake < start-point for snake).
This allows you to ignore being at the tail of snake, because the tail will be updated (if required) when you'll reach the head of the snake and everything is recalculated. Also, since tail is updated only on getting lower value, no such tail will be updated more than once usually.
While implementing, you need to consider all the three points mentioned above simultaneously for each square. Also, do remember to consider the current value of the square to find minimum each time.
Snakes and Ladders: The Quickest Way Up
You are viewing a single comment's thread. Return to all comments →
DP gives an efficient solution to the problem (solves all test cases in 0s with C). The basic idea is as follows :
1) Calculate number of minimum moves required to reach each every square, starting from 1 till 100 (square 100 gives the answer). Initialize all the sqaures with a "very high value" to begin with.
2) Ladders : If the current square is starting-point of ladder, update the square at the end-point of the ladder (note : end-point of ladder > start-point of ladder). If the minimum moves required to reach the current square is "c" and the current value of square at the end-point of ladder is "x" then the updated value should be min(c,x).
3) Snakes : If the current square is starting-point for snake, update the square at the end-point (tail) of the snake only if the moves required to reach the current square is less than the "value of square at the tail of the snake". If the value is updated, start calculating the moves from the tail of the snake (end-point for snake < start-point for snake).
This allows you to ignore being at the tail of snake, because the tail will be updated (if required) when you'll reach the head of the snake and everything is recalculated. Also, since tail is updated only on getting lower value, no such tail will be updated more than once usually.
While implementing, you need to consider all the three points mentioned above simultaneously for each square. Also, do remember to consider the current value of the square to find minimum each time.
Happy Coding !!!