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.
This is a setback, but not a fatal one. I used BFS, but to make that work, you have to do the following:
if you can get from square i to square j in one die roll and j begins a ladder or a snake to square k, add in your adjacency matrix A[i,k] = 1 and make A[i,j] = 0 (the idea is that if we can hop onto a ladder or snake, cut out the middleman and just go directly to its destination. Also we can't go to the space with the start of a ladder or snake because that would imply we didn't follow the ladder or snake to its destination). This way we do not need edge weights and so we can use simple BFS. Dikjstra's is a little overkill with only 1's and 0's.
Snakes and Ladders: The Quickest Way Up
You are viewing a single comment's thread. Return to all comments →
This is a setback, but not a fatal one. I used BFS, but to make that work, you have to do the following: if you can get from square i to square j in one die roll and j begins a ladder or a snake to square k, add in your adjacency matrix A[i,k] = 1 and make A[i,j] = 0 (the idea is that if we can hop onto a ladder or snake, cut out the middleman and just go directly to its destination. Also we can't go to the space with the start of a ladder or snake because that would imply we didn't follow the ladder or snake to its destination). This way we do not need edge weights and so we can use simple BFS. Dikjstra's is a little overkill with only 1's and 0's.