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

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions[bot]]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!