Snake and Ladder Problem

Problem statement

Given a snake and ladder coordinates which represent the actual snake and ladder board, find the minimum number of dice throws required to reach the destination cell from source cell. This problem can be easily solved bu using 0-1 BFS.

Example Input

Size = 100
Snakes = {{24, 14},{56, 21}, {88, 34},{99, 3}}
Ladders = {{4, 57},{18, 36},{44, 97},{67, 88}}

Expected Output

7

Implementation in Python

class Board(object): 
    def __init__(self, v = 0, dist = 0): 
        self.v = v 
        self.dist = dist 
def SnakeLadder(board, Size): 
    
    check_visited = [False] * Size 
  
    Entry = [] 
  
    check_visited[0] = True
    Entry.append(Board(0, 0)) 
    while Entry: 
        Value = Entry.pop(0) 
        v = Value.v 
        if v == Size - 1: 
            break
  
        j = v + 1
        while j <= v + 6 and j < Size: 
          
            if check_visited[j] is False: 
                  
                a = Board() 
                a.dist = Value.dist + 1
                check_visited[j] = True
  
                a.v = board[j] if board[j] != -1 else j 
  
                Entry.append(a) 
  
            j += 1
  
    return Value.dist 
  
# driver code 
Size = 100
board = [-1] * Size 
  
# Ladders 
board[4] = 57
board[18] = 36
board[44] = 97
board[67] = 88
  
# Snakes 
board[24] = 14
board[56] = 21
board[88] = 34
board[99] = 3
  
print(SnakeLadder(board, Size))
[gravityforms id="5" description="false" titla="false" ajax="true"]