Link: https://leetcode.com/problems/snakes-and-ladders/
Solution:
Intuition
Classic shortest path problem BFS problem with some edge cases in the way it’s set up. Because the positions are 1 indexed, its way more convenient to flatten the board into a 1d array and use the snake/ladders to index directly into the respective position.
Once that’s done, we simply perform a BFS starting a position 1 (or 0 if 0-indexed). We add to the queue the first 6 positions in front of the current position. If one of those positions is either a snake or a ladder, we add the value to the queue.
Keep a visited set on the positions to prevent cycles. For some reason that I can’t understand, modifying the board in-place for cycle prevention fails some test cases…just keep it simple and use a set.
Implementation
Visual