[FEATURE REQUEST] Snake and Ladder board game graph problem

[sherlockwayne]

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]

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:

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

2. 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.

3. 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.