[FEATURE REQUEST] Snake and Ladder board game graph problem
Opened this issue · 1 comments
sherlockwayne commented
What would you like to Propose?
Problem statement: Given a snake and ladder board, find the minimum number of dice throws required to reach the destination or last cell from the source or 1st cell.
Input:
N->total Number of snakes and ladders
arr[] of 2N size where 2i and (2*i + 1)th values denote the starting and ending point respectively of ith snake or ladder
Issue details
Graph and BFS based problem
Additional Information
No response
aayu5hgit commented
Hey @sherlockwayne
Please assign this to me, I've the logic ready with me which has a time and space complexity of O(N).
This can be solved efficiently using a Breadth-First Search (BFS) approach.
Each cell on the board is treated as a node, and a dice throw represents an edge between nodes.
Approach:
- Graph Representation:
- Treat the board as a graph with N vertices where N is the number of cells.
- Every possible dice throw from a cell leads to an edge to one of the next 6 cells (unless there’s a snake or a ladder).
- Breadth-First Search (BFS):
- Since BFS explores nodes level by level and finds the shortest path in an unweighted graph, it’s perfect for this problem.
- Snakes and Ladders:
-When a snake or ladder is encountered, you "teleport" to the destination of that snake/ladder.
- We must map these teleportations before running BFS.