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 queueand add the startingsquareto it. 2. Create a visitedarray 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 s**pace 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

Table of Contents

## 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

Reading your article has greatly helped me, and I agree with you. But I still have some questions. Can you help me? I will pay attention to your answer. thank you.

Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.