The problem “Snakes and Ladders” is a problem where the goal is to find the minimum number of dice rolls required to reach the final square in a game of snakes and ladders. The game is represented by a square grid with snakes and ladders on some of the squares. Landing on a ladder square will take you to a higher square, while landing on a snake square will take you to a lower square.
One way to solve this problem is to use Breadth-first search (BFS) algorithm, where we start from the starting square and explore all the neighboring squares and add them to a queue. Then we take the first element from the queue, mark it as visited and repeat the process.
Here is the pseudo-code / step by step of the solution:
1. Create a queue and add the starting square to it.
2. Create a visited array and mark the starting square as visited.
3. While the queue is not empty:
- Dequeue the front element from the queue
- For all possible dice rolls (1 to 6) from the current square:
- Calculate the next square by adding the dice roll to the current square
- If the next square is out of the board, continue
- If the next square has a ladder or snake, update the next square to the corresponding square
- If the next square is not visited, mark it as visited and add it to the queue
4. Return the number of rolls required to reach the final square
The time complexity of this algorithm is O(n^2) where n is the number of cells in the board. This is because, in the worst case, we might have to visit all the cells in the board.
The space complexity of this algorithm is O(n) where n is the number of cells in the board. This is because we use a queue and a visited array to store the cells that we have visited.
It’s worth noticing that there is another algorithm that solves the problem with a time complexity of O(n) which is called Bellman Ford Algorithm and is used to solve the single-source
c++ Solution :
typedef pair<int,int> Pi;
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int rows=board.size(), cols = board[0].size(), target=rows*cols, r, c, p;
vector<int> visited(rows*cols + 1); // cells on board start from 1
// queue contains <priority, square> sorted ascending by priority
// prio = #steps * 1000 + (500 - square);
// number of steps is critical and adds 1000; 500 is selected as it is higher than the max cell (20*20=400)
priority_queue<Pi, vector<Pi>, greater<Pi>> q;
q.push(make_pair(0,1)); // 0 steps to position 1
visited[1] = true;
while(q.size())
{
auto step_pos = q.top(); q.pop();
int s = step_pos.first/1000 + 1;
for(int i=1; i<=6; i++)
{
auto p = step_pos.second+i;
if(visited[p]) continue;
visited[p] = true;
r = rows - (p-1) / cols - 1;
c = (p-1) % cols;
if((rows-r-1)%2) c = cols - c - 1; // change direction for odd lines
int ladder = board[r][c];
if(ladder>0 && ladder<=target)
p = ladder; // no update for steps. allow to come here again with a dice
if(p == target) return s;
q.push(make_pair(s*1000+500-p, p));
}
}
return -1;
}
};java
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
boolean[] visited = new boolean[n * n + 1];
for (int move = 0; !queue.isEmpty(); move++) {
for (int size = queue.size(); size > 0; size--) {
int num = queue.poll();
if (visited[num]) continue;
visited[num] = true;
if (num == n * n) return move;
for (int i = 1; i <= 6 && num + i <= n * n; i++) {
int next = num + i;
int value = getBoardValue(board, next);
if (value > 0) next = value;
if (!visited[next]) queue.offer(next);
}
}
}
return -1;
}
private int getBoardValue(int[][] board, int num) {
int n = board.length;
int r = (num - 1) / n;
int x = n - 1 - r;
int y = r % 2 == 0 ? num - 1 - r * n : n + r * n - num;
return board[x][y];
}
}Python
from queue import Queue
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
dist = [float('inf')] * (n*n)
dist[0] = 0
q = Queue()
q.put(0)
while not q.empty():
curr = q.get()
if curr == n*n - 1:
return dist[curr]
for i in range(curr+1, min(curr+7, n*n)):
next_ = self.getNext(i, n, board)
if dist[next_] > dist[curr] + 1:
dist[next_] = dist[curr] + 1
q.put(next_)
return -1
def getNext(self, i: int, n: int, board: List[List[int]]) -> int:
row = n-1-(i-1)//n
col = (row%2 == n%2) * (i-1) % n or n-1-(i-1) % n
num = board[row][col]
return i if num == -1 else num-1
Javascript
class Solution {
snakesAndLadders(board) {
const n = board.length;
const dist = new Array(n*n).fill(Number.MAX_SAFE_INTEGER);
const q = [];
q.push(0);
dist[0] = 0;
while (q.length > 0) {
const curr = q.shift();
if (curr === n*n - 1) {
return dist[curr];
}
for (let i = curr + 1; i <= Math.min(curr + 6, n*n - 1); i++) {
const next = this.getNext(i, n, board);
if (dist[next] > dist[curr] + 1) {
dist[next] = dist[curr] + 1;
q.push(next);
}
}
}
return -1;
}
getNext(i, n, board) {
const row = n - 1 - Math.floor((i-1)/n);
const col = (row % 2 === n % 2) ? (i-1) % n : n - 1 - (i-1) % n;
const num = board[row][col];
return (num === -1) ? i : num-1;
}
}
Dart
List of Some important Leet code Questions:
- Leet Code 2612 Minimum Reverse Operations
- Leet code 206 Reverse Linked List
- Leet Code 420 Strong Password Checker
- Leetcode 1359 Count All Valid Pickup and Delivery
- Leet code 799. Champagne Tower
- LeetCode 389. Find The Difference
- Leetcode 775. Find The Global and Local Inversions
- Leetcode 316. Remove Duplicate Letters
- LeetCode 2233 Maximum Product After K Increments
- LeetCode 880. Decoded String at Index
- LeetCode 905. Sort Array By Parity
- LeetCode 896. Monotonic Array
- LeetCode 132. Pattern