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.

# Snakes and Ladders: The Quickest Way Up

# Snakes and Ladders: The Quickest Way Up

#### Sort by

recency

#### |

#### 250 Discussions

#### |

Please Login in order to post a comment

"Snakes and Ladders: The Quickest Way Up" problem, we can use the Breadth-First Search (BFS) algorithm. Below is the PHP solution for this problem:

## Explanation:

Initialization:`board`

array stores the effect of ladders and snakes on each cell.`queue`

is used for BFS, initialized with the starting position (1, 0) representing the start of the board and 0 moves.`visited`

array keeps track of visited cells to avoid revisiting them.Setup Ladders and Snakes:BFS to Find Shortest Path:Handling Input:`readInput`

function reads the input from standard input and processes it.`quickestWayUp`

function for each test case and print the result.## Pthon

BFS

Rust is generally a bit verbose. The execution time is nice, though. time ./target/release/rust < input_1.txt (test case #1) real 0m0.016s user 0m0.006s sys 0m0.008s

I noticed HackerRank is passing on all cases for a code that is incorrect.

To solve this problem, I implemented the following code:

But it resulted in a wrong answer for the following input:

You can notice I have a set of visited nodes, and that I will process each node of the graph only once. Also, I'm processing the nodes in the order they are being added to the queue.

When processing node 1, I will add to the queue nodes from 2 to 7 with one roll. When processing node 6, I will add node 12 in the queue with two rolls. But I can arrive in node 12 with only one roll, by falling on node 7 after the first roll and use the ladder. Since node 12 was first added to the queue with 2 rolls, I will process it using two rolls, and will not process it again with 1 roll (I have a continue on the code).

For the input I provided, it will result in an answer of 18. And HackerRank is accepting the solution.

But I can arrive on node 100 with only 13 rolls. The following method is correct and generates the answer of 13.

from collections import deque def quickestWayUp(ladders, snakes):