< Back




909. Snakes and Ladders

Not the regular snakes and ladders game, thankfully, since we can only travel towards the end of the
board. We start at the first square, 1 - from there we can travel to squares in the range
(1, min(1 + 6, n * n)). If a square we visit is a ladder or snake, instead of landing on the next
square, we land wherever the ladder or snake takes us - this information is stored within the board.

We solve this problem with BFS, however, we have to do a bit of preprocessing of the input to make
it easy to solve with BFS. We walk the board along its rows and columns in the order that the
numbers are printed - starting from the bottom left of the board towards the right, then as we go
up a level we walk from the right to the left. We maintain a 1D array with the labels of the board
cells being the indices, and we store row and column for the label in each 1D array cell.

We maintain a distance array that will be used for our final answer, and conduct our BFS. At each
label we calculate the neighbors, from the range mentioned earlier, and determine their rows and
columns. We check to see if they're a ladder or snake, updating our destination accordingly. If this
destination hasn't been visited, we update the distance array at this destination with the steps
we've taken so far. Finally, we add this destination to our queue for the next step.

After completing our BFS, we return the distance array at the last cell of the board, which will be
the length of the shortest path to the end of the board.

The solution is as follows:


  class Solution:
      def snakesAndLadders(self, board: List[List[int]]) -> int:
          n = len(board)
          cells = [None] * (n * n + 1)
          columns = list(range(n))
          label = 1

          for row in range(n - 1, -1, -1):
              for col in columns:
                  cells[label] = (row, col)
                  label += 1

              columns.reverse()

          queue = [1]
          distance = [-1] * (n * n + 1)
          distance[1] = 0

          while queue:
              curr_queue, queue = queue, []

              for node in curr_queue:
                  for neighbor in range(node + 1, min(node + 6, n * n) + 1):
                      nrow, ncol = cells[neighbor]
                      destination = (
                          board[nrow][ncol] if board[nrow][ncol] != -1 else neighbor
                      )

                      if distance[destination] == -1:
                          distance[destination] = distance[node] + 1
                          queue.append(destination)

          return distance[n * n]


_ Time Complexity:

  O(n ** 2) - The complexity of BFS, where n are the edges and n are the nodes.

_ Space Complexity:

  O(n ** 2) - We maintain a 1D array of size n * n to track distance and transform the board into
  a 1D array of size n * n to track the cells.