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))