Dare2Solve
The problem involves playing a game on an n x n
board where the cells contain either -1 (indicating an empty cell) or a positive integer (indicating a snake or a ladder that transports the player to another cell). The goal is to determine the minimum number of moves required to reach the last cell from the first cell.
The problem can be approached as a shortest path problem on an unweighted graph, where each cell in the board represents a node, and each move (from 1 to 6 cells forward) represents an edge. Breadth-First Search (BFS) is a suitable algorithm to find the shortest path in an unweighted graph.
O(V + E)
time complexity, where V
is the number of cells (n*n
) and E
is the number of possible moves (6 per cell). Hence, O(n^2)
.O(n^2)
.class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
set<int> visited;
auto getPos = [&](int pos) {
int row = (pos - 1) / n;
int col = (pos - 1) % n;
if (row % 2 == 1) col = n - 1 - col;
row = n - 1 - row;
return make_pair(row, col);
};
queue<pair<int, int>> q;
q.push({1, 0});
while (!q.empty()) {
auto [pos, moves] = q.front();
q.pop();
for (int i = 1; i < 7; ++i) {
int newPos = i + pos;
auto [r, c] = getPos(newPos);
if (board[r][c] != -1) newPos = board[r][c];
if (newPos == n * n) return moves + 1;
if (!visited.count(newPos)) {
visited.insert(newPos);
q.push({newPos, moves + 1});
}
}
}
return -1;
}
};
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
def getPos(pos: int) -> (int, int):
row = (pos - 1) // n
col = (pos - 1) % n
if row % 2 == 1:
col = n - 1 - col
row = n - 1 - row
return row, col
visited = set()
queue = deque([(1, 0)]) # (position, moves)
while queue:
pos, moves = queue.popleft()
for i in range(1, 7):
newPos = pos + i
if newPos > n * n:
break
r, c = getPos(newPos)
if board[r][c] != -1:
newPos = board[r][c]
if newPos == n * n:
return moves + 1
if newPos not in visited:
visited.add(newPos)
queue.append((newPos, moves + 1))
return -1
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
Set<Integer> visited = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{1, 0}); // Start from position 1 with 0 moves
while (!queue.isEmpty()) {
int[] current = queue.poll();
int pos = current[0];
int moves = current[1];
for (int i = 1; i <= 6; i++) {
int newPos = pos + i;
if (newPos > n * n) break;
int[] coordinates = getPos(newPos, n);
int r = coordinates[0];
int c = coordinates[1];
if (board[r][c] != -1) newPos = board[r][c];
if (newPos == n * n) return moves + 1;
if (!visited.contains(newPos)) {
visited.add(newPos);
queue.offer(new int[]{newPos, moves + 1});
}
}
}
return -1;
}
private int[] getPos(int pos, int n) {
int row = (pos - 1) / n;
int col = (pos - 1) % n;
if (row % 2 == 1) col = n - 1 - col;
row = n - 1 - row;
return new int[]{row, col};
}
}
var snakesAndLadders = function (board) {
let n = board.length;
let set = new Set();
let getPos = (pos) => {
let row = Math.floor((pos - 1) / n)
let col = (pos - 1) % n
col = row % 2 == 1 ? n - 1 - col : col;
row = n - 1 - row;
return [row, col]
}
let q = [[1, 0]]
while (q.length > 0) {
[pos, moves] = q.shift();
for (let i = 1; i < 7; i++) {
let newPos = i + pos;
let [r, c] = getPos(newPos);
if (board[r][c] != -1) newPos = board[r][c]
if (newPos == n * n) return moves + 1;
if (!set.has(newPos)) {
set.add(newPos)
q.push([newPos, moves + 1])
}
}
}
return -1
};