Problem Explanation

In this problem, you have a grid (NxN) representing a board game. The game starts in the first number and ends in the last one (N*N). Your movements in the game are dictated by the result of a 6-sided die roll; you can move from 1 to 6 positions forward. Some cells have "snakes" or "ladders", understood as numbers different from -1, that teleport you to another location in the board. Once you reach a cell having a ladder or snake, you move to the destination but don't continue moving even if the destination is the start of another snake or ladder.

The problem requires finding the minimum number of steps needed to win the game (reach the N*N cell). If it is not possible to reach the end, return -1.

Solution Approach

The problem can be solved using a Breadth-first search (BFS) algorithm. BFS is a type of graph traversal algorithm that explores all the vertices of a graph in breadth-first order, i.e., it explores all the vertices at the present depth before moving on to vertices at the next depth level. It uses a Queue data structure to keep track of vertices not yet visited. Here we are treating the board game as a graph where the numbers represent nodes and the edges are the possible movements.

The first step is to transform the given 2D grid into a 1D array. This way it will be easier to track all possible moves (from 1 to 6) from the current position. You just need to increment the current index to get the next positions.

On the BFS, each level represents one move in the game. We start the process by adding the first node to the queue. For each level, we check all possible next positions (from 1 to 6) and add the valid ones to the queue, marking them as visited so we don't process them again.

The process ends when we have no more nodes to process (return -1) or when we find the end of the board (return the number of levels processed).

Python Solution

1
2 python
3from collections import deque
4
5class Solution:
6    def snakesAndLadders(self, board):
7        N = len(board)
8        moves = [0] * (N*N)
9        
10        # Reshape the board into a 1D array
11        i, j, even = N - 1, 0, 0
12        for _ in range(N*N):
13            if board[i][j] > 0: moves[even] = board[i][j] - 1
14            else: moves[even] = even
15                
16            # If it is an even row move left, else move right
17            if i % 2 == 0: j += 1
18            else: j -= 1
19                
20            # If we are out of bounds, change the row and adjust new direction 
21            if j == N or j < 0: i -= 1; even += 1; j = N - 1 if j == N else 0
22                
23            even += 1
24                
25        # BFS
26        queue, moves[0] = deque([0]), -1
27        while queue:
28            square = queue.popleft()
29            if square == N*N - 1: return moves[square]
30                
31            # Explore all possible moves from 1 to 6.
32            for i in range(1, 7):
33                if square + i < N*N and moves[square + i] != -1:
34                    queue.append(square + i)
35                    moves[square + i] = -1
36                        
37        return -1

C++ Solution

1
2 c++
3#include <vector>
4#include <queue>
5
6using namespace std;
7
8class Solution {
9public:
10    int snakesAndLadders(vector<vector<int>>& board) {
11        int n = board.size();
12        vector<int> moves(n * n);
13        bool left_to_right = true;
14        int index = 0;
15        
16        // Reshape the board into a 1D vector
17        for(int i = n - 1; i >= 0; i--) {
18            if(left_to_right) {
19                for(int j = 0; j < n; j++) {
20                    moves[index++] = (board[i][j] == -1 ? -1 : board[i][j] - 1);
21                }
22            } else {
23                for(int j = n - 1; j >= 0; j--) {
24                    moves[index++] = (board[i][j] == -1 ? -1 : board[i][j] - 1);
25                }
26            }
27            left_to_right = !left_to_right;
28        }
29        
30        queue<int> q;
31        q.push(0);
32        moves[0] = -2;  // Mark first move as visited
33 
34        // BFS
35        int steps = 0;
36        while(!q.empty()) {
37            
38            int size = q.size();
39            while(size--) {
40                int cur = q.front(); q.pop();
41                if(cur == n * n - 1) return steps;  // Found the end
42                
43                for(int i = 1; i <= 6; i++) {
44                    int next = cur + i;
45                    if(next < n * n && moves[next] != -2) {
46                        q.push(moves[next] == -1 ? next : moves[next]);
47                        moves[next] = -2;
48                    }
49                }
50            }
51            steps++;
52        }
53        
54        return -1;
55    }
56};

Java Solution

1
2 java
3import java.util.*;
4
5class Solution {
6    public int snakesAndLadders(int[][] board) {
7        int N = board.length;
8        int[] moves = new int[N*N];
9        boolean rightToLeft = false;
10        int index = 0;
11        
12        // Reshape the board into a 1D array
13        for (int i = N - 1; i >= 0; i--) {
14            if (rightToLeft) {
15                for (int j = N - 1; j >= 0; j--) {
16                    moves[index++] = board[i][j] == -1 ? -1 : board[i][j] - 1;
17                }
18            } else {
19                for (int j = 0; j < N; j++) {
20                    moves[index++] = board[i][j] == -1 ? -1 : board[i][j] - 1;
21                }
22            }
23            rightToLeft = !rightToLeft;
24        }
25        
26        Queue<Integer> q = new LinkedList<>();
27        q.offer(0);
28        moves[0] = -2;  // Mark first move as visted
29        
30        // BFS
31        int steps = 0;
32        while (!q.isEmpty()) {
33            for (int size = q.size(); size > 0; size--) {
34                int curr = q.poll();
35                if (curr == N*N - 1) return steps;  // Found the end
36                
37                for (int i = 1; i <= 6; i++) {
38                    int next = curr + i;
39                    if (next < N*N && moves[next] != -2) {
40                        q.offer(moves[next] == -1 ? next : moves[next]);
41                        moves[next] = -2;
42                    }
43                }
44            }
45            steps++;
46        }
47        
48        return -1;
49    }
50}

JavaScript Solution

1
2 javascript
3var snakesAndLadders = function(board) {
4    var moves = flattenBoard(board);
5    var queue = [0];
6    var level = 0;
7    var visited = new Set();
8
9    while (queue.length) {
10        var nextQueue = [];
11        
12        for (var pos of queue) {
13            if (pos == moves.length - 1) return level;
14            
15            for (var move = 1; move <= 6; move++) {
16                var nextPos = pos + move;
17                
18                if (nextPos < moves.length && !visited.has(nextPos)) {
19                    visited.add(nextPos);
20                    nextQueue.push(moves[nextPos] == -1 ? nextPos : moves[nextPos]);
21                }
22            }
23        }
24        
25        level++;
26        queue = nextQueue;
27    }
28
29    return -1;
30};
31
32var flattenBoard = function(board) {
33    var rowRight = true;
34    var moves = [];
35    
36    for (var i = board.length - 1; i >= 0; i--) {
37        var row = board[i];
38        
39        if (rowRight) moves.push(...row);
40        else moves.push(...row.reverse());
41        
42        rowRight = !rowRight;
43    }
44    
45    return moves;
46};

All these solutions have a time and space complexity of O(N^2), where N is the length of the board. This is because we need to process each cell in the board, and in the worst case scenario, we might need to keep all of them in the queue. However, because we mark the cells as visited as soon as we add them to the queue, we ensure that each one is processed only once, optimising the efficiency of the algorithm.