Home » leet code » LeetCode: Solving Snakes and Ladders with BFS Algorithm

LeetCode: Solving Snakes and Ladders with BFS Algorithm

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:

Leave a Reply