Leetcode 909. Snakes and Ladders
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.