Passing Test Case 0 and Example || Failing Test Case 1

#1

Question:
https://online.codingblocks.com/app/player/65729/content/108580/5083/code-challenge

My solution:

#2

hii @Abhishek.1514 how are you figuring out which place has a snake and which place has a ladder? Also please explain your logic a bit as it seems slightly different from what bhaiya showed in the hint video

#3

If its a snake the next square will have a lower value than the cur square.

#4

I go only forward. This is a bfs approach. dist stores the number of die throws it took to reach here. If there is a special edge originating from the cur square i go along that edge if it is a ladder. I do nothing if it is a snake. Hence the path forward from that square is abandoned as it will definitely need more number of die throws. If it doesnt have a special edge i go to all the squares not yet visited that are possible to visit from cur square with a die throw of 1 to 6

#5

hi @Abhishek.1514 but there is no guarantee that if you choose a ladder instead of simply moving forward, or choosing some other number, then you will end up with the shortest path.
for eg suppose you are at 1. There is a ladder present at 2 that goes upto 35 and there is also a ladder present at 6 that goes up to 99. If you choose to go to 6, then you will simple reach 100 in 2 steps (1->6,99->100)
but it will take more steps if you choose to climb the ladder at 2, and go to 35.
According to your approach, you will see that ladder is present at 2 and simply climb it.
This is just an example, are you getting where your approach might fail?

What you can instead do is, form edges between possible places where you may end up because of snakes/ladders as told in the hint video. Apply BFS shortest path algorithm on that graph simply, it will work for all cases. The only trick is how to make the initial board. That is also quite simple. Once you do that part, rest of it is just basic BFS

#6

@Abhishek.1514 implementation using the method I told above: https://ide.codingblocks.com/s/300743

#7

I figured out the problem. The case you specified is handled by my code. My skipping snakes thinking obviously they will only ever increase the number of die throws was wrong. The case where ladders are between 2 to 35 and 20 to 99 with snake from 36 to 19. In this, I get 4 if i use the snake because i get to 20 quicker (2 die throws) then if i dont use the snake (3 throws)

#8

hi @Abhishek.1514 try to implement it by first making the board with the help of coordinates of snakes and ladders