LeetCode: Solving Snakes and Ladders with BFS Algorithm

8 / 100

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

1 thought on “LeetCode: Solving Snakes and Ladders with BFS Algorithm”

  1. The output of this code would be the minimum number of moves required to reach the last cell of the board, starting from the first cell (1), using the rules of the game Snakes and Ladders. If it is not possible to reach the last cell, the output would be -1. The code uses a breadth-first search algorithm to explore the board, with the queue storing the current position on the board and the visited array keeping track of the cells that have already been visited to prevent going in a cycle. The getBoardValue method is used to determine the next cell to move to, based on the value of the current cell on the board (either a ladder or a snake) or the next cell in sequence if there is no value.

Leave a Comment