Problem statement

https://leetcode.com/problems/snakes-and-ladders/

Solution

The idea is to use bfs, because we are asked to find the shortest distance. First of all we need to create list l of correct order of cells. Then we use classical bfs, where step is either move from 1 to 6 where we check that if new position have ladder or snake, we need to go to new position. Also we can have loops, so we use visited set to avoid infinite loop.

Complexity

It is O(n^2) for time and space.

Code

class Solution:
    def snakesAndLadders(self, board):
        l = [0]
        for i, row in enumerate(board[::-1]):
            l += row[::1 - (i%2)*2]
        
        n = len(board)    
        queue = deque([(0, 1)])
        visited = set([1])
        
        while queue:
            steps, pos = queue.popleft()
            if pos == n*n: return steps
            
            for i in range(pos + 1, min(pos + 7, n*n + 1)):
                cand = i if l[i] == -1 else l[i]
                if cand not in visited:
                    queue.append((steps + 1, cand))
                    visited.add(cand)

        return -1