Leetcode 909: Snakes and Ladders
You are given an n x n integer matrix
board where the cells are numbered from 1 to n² in a zigzag pattern starting from the bottom-left corner. Each cell may contain either -1 (indicating no special feature) or a number indicating a snake or ladder destination. You start at square 1 and can roll a 6-sided die to move between 1 and 6 steps. If you land on a square with a snake or ladder, you must move to its destination. Determine the minimum number of dice rolls needed to reach the final square n². Return -1 if it is not possible.Problem
Approach
Steps
Complexity
Input: An `n x n` matrix `board` where each cell represents a square in the game, containing either `-1` or a number indicating a snake or ladder destination.
Example: Input: board = [[-1,-1,-1],[-1,-1,-1],[-1,-1,2]]
Constraints:
• n == board.length == board[i].length
• 2 <= n <= 20
• board[i][j] is either -1 or in the range [1, n²]
• Squares 1 and n² are not the start of any snake or ladder.
Output: The minimum number of dice rolls required to reach the final square `n²`. If unreachable, return -1.
Example: Output: 3
Constraints:
Goal: Use Breadth-First Search (BFS) to calculate the minimum steps to reach square `n²`.
Steps:
• Convert the 2D matrix to a 1D representation for easier traversal.
• Use BFS starting from square 1, keeping track of visited squares to avoid revisits.
• For each square, simulate a dice roll (1 to 6 steps) and determine the next position.
• If a square has a snake or ladder, move to its destination; otherwise, move normally.
• If the final square `n²` is reached, return the current roll count. If the queue is empty and `n²` is not reached, return -1.
Goal: Limitations and conditions for the game board and movement.
Steps:
• The board is always square (n x n).
• Values in the board are either `-1` or valid destinations within the range of the board.
• There are no snakes or ladders at squares 1 and `n²`.
Assumptions:
• The board dimensions are valid (n x n).
• Dice rolls always provide up to 6 possible moves unless constrained by board size.
• Input: Input: board = [[-1,-1,-1],[6,-1,-1],[-1,-1,2]]
• Explanation: Start at square 1. Move to square 2 and follow the ladder to square 6. Then, roll to square 7 and follow the snake to square 2. Finally, roll to square 9 to win in 3 moves.
• Input: Input: board = [[-1,-1],[-1,-1]]
• Explanation: There are no snakes or ladders. The quickest path is to roll the dice 2 times to reach square 4.
Approach: Use BFS to explore the shortest path to square `n²` in terms of dice rolls, accounting for snakes and ladders.
Observations:
• This problem can be modeled as a shortest-path problem in an unweighted graph.
• Snakes and ladders alter the natural progression, requiring specific handling.
• Using BFS ensures we explore the shortest path first due to its level-order traversal.
Steps:
• Define a helper function to convert a square number to its corresponding row and column in the zigzag board layout.
• Use BFS to traverse from square 1 to `n²`.
• For each square, calculate potential destinations (up to 6 moves ahead).
• Check if the destination square has a snake or ladder and adjust the position accordingly.
• Keep track of visited squares to prevent redundant computations.
Empty Inputs:
• The board has the smallest possible size (2x2).
Large Inputs:
• The board has the largest possible size (20x20) with complex snake and ladder placements.
Special Values:
• The board has no snakes or ladders.
• The board is entirely filled with snakes or ladders, forcing specific paths.
Constraints:
• The dice roll moves beyond the board's bounds.
void getCoordinate(int n, int s, int &row, int &col) {
row = n-1-(s-1)/n;
col = (s-1)%n;
if((n%2 ==1 && row%2==1) || (n%2==0 && row%2==0))
col= n-1-col;
}
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
vector<bool> seen(n*n+1, false);
seen[1] = true;
queue<pair<int, int>> q;
q.push({1, 0});
while(!q.empty()) {
pair<int, int> p = q.front();
q.pop();
int row, col, s = p.first, dist = p.second;
if(s == n*n)
return dist;
for(int i = 1; s+i<= n *n && i<=6;i++) {
getCoordinate(n, s+i, row, col);
int sfinal = board[row][col] == -1? s+i:board[row][col];
if(seen[sfinal] == false) {
seen[sfinal] = true;
q.push({sfinal, dist + 1});
}
}
}
return -1;
}
1 : Function Definition
void getCoordinate(int n, int s, int &row, int &col) {
Define the function `getCoordinate` to compute the row and column based on the given board size and the cell number.
2 : Formula
row = n-1-(s-1)/n;
Calculate the row of the cell based on the board size and the cell number.
3 : Formula
col = (s-1)%n;
Calculate the column of the cell based on the board size and the cell number.
4 : Conditional
if((n%2 ==1 && row%2==1) || (n%2==0 && row%2==0))
Check if the row needs to be reversed based on the board size and row parity.
5 : Action
col= n-1-col;
Reverse the column if the row direction is reversed.
6 : Function Definition
int snakesAndLadders(vector<vector<int>>& board) {
Define the `snakesAndLadders` function to solve the problem using BFS.
7 : Variable Initialization
int n = board.size();
Initialize `n` as the size of the board.
8 : Data Structure
vector<bool> seen(n*n+1, false);
Create a vector `seen` to track visited cells.
9 : Action
seen[1] = true;
Mark the first cell as visited.
10 : Queue
queue<pair<int, int>> q;
Initialize a queue to store the current cell and the number of moves taken to reach it.
11 : Queue Operation
q.push({1, 0});
Push the starting cell (1, 0 moves) into the queue.
12 : Loop
while(!q.empty()) {
Start a while loop to process cells in the queue.
13 : Queue Operation
pair<int, int> p = q.front();
Retrieve the front element of the queue.
14 : Queue Operation
q.pop();
Pop the front element from the queue.
15 : Variable Assignment
int row, col, s = p.first, dist = p.second;
Extract the current cell and distance from the pair.
16 : Conditional
if(s == n*n)
Check if the current cell is the last cell.
17 : Return
return dist;
Return the current distance if the last cell is reached.
18 : Loop
for(int i = 1; s+i<= n *n && i<=6;i++) {
Loop through the next possible cells (dice rolls 1 to 6).
19 : Function Call
getCoordinate(n, s+i, row, col);
Call `getCoordinate` to compute the row and column for the new cell.
20 : Action
int sfinal = board[row][col] == -1? s+i:board[row][col];
Determine the final cell based on ladders or snakes.
21 : Conditional
if(seen[sfinal] == false) {
Check if the final cell has already been visited.
22 : Action
seen[sfinal] = true;
Mark the final cell as visited.
23 : Queue Operation
q.push({sfinal, dist + 1});
Push the final cell into the queue with the updated distance.
24 : Return
return -1;
Return -1 if no solution is found.
Best Case: O(n²)
Average Case: O(n²)
Worst Case: O(n²)
Description: Each square is visited once, and up to 6 moves are checked for each square.
Best Case: O(n²)
Worst Case: O(n²)
Description: The BFS queue and visited array each store up to n² elements.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus