Snake and Ladder Problem Statement
Given a Snake and Ladder Board with 'N' rows and 'N' columns filled with numbers from 1 to N*N starting from the bottom left of the board, and alternating direction each row, determine the minimum number of dice throws required to reach the last cell. You can control the dice outcome, landing between 1 and 6 ahead of your current position. Some squares might contain snakes or ladders which alter your next position.
Input:
The first line of input contains a single integer 'N' representing the number of rows and columns.
The next N lines each contain N integers describing the board configuration.
Output:
The minimum number of throws needed to reach the last cell. Print -1 if it is impossible.
Example:
Input:
3
-1 1 -1
-1 -1 9
-1 4 -1
Output:
2
Explanation:
Starting on square 1, with control over the dice, you can move to square 2 and take the ladder to 4, then move to square 10 (last cell).
Constraints:
1 <= N <= 10^2
1 <= board[i][j] <= N*N or board[i][j] = -1
Note:
-1 indicates no snake or ladder on that board square. Landing on a square with a snake or ladder moves you to the destination of that snake or ladder, but you do not chain moves beyond that.
Find the minimum number of dice throws required to reach the last cell on a Snake and Ladder board.
Use Breadth First Search (BFS) to explore all possible paths with minimum dice throws.
Keep track of v...read more
Top Microsoft Corporation SDE-2 interview questions & answers
Popular interview questions of SDE-2
Top HR questions asked in Microsoft Corporation SDE-2
Reviews
Interviews
Salaries
Users/Month