Snake and Ladder BFS

Problem

Find the minimum number of dice rolls to travel from square 1 to square n*n on a snakes-and-ladders board.

board is an n by n grid with -1 for a plain square or a target square number for a snake or ladder. Rows alternate direction starting left to right on the bottom row. Each roll moves 1 to 6 squares. Return -1 when the last square cannot be reached.

Hint

Map each board row to square numbers, then BFS over dice outcomes with jumps applied.

Test cases

case 1

in: [[[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1]]]

expected: 4

case 2

in: [[[-1]]]

expected: 0

case 3

in: [[[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]]]

expected: 2

case 4

in: [[[-1,-1],[-1,4]]]

expected: 1

Starter codePython

def snakes_and_ladders(board):
    # Your code here
    pass

4 test cases · run your code against them in the editor