Today, I found a very interesting problem on LeetCode — "Snakes and Ladders" (Problem #909).
We are all familiar with the game of Snakes and Ladders and how we play it using a dice. Well, this question actually asks you to simulate the game and find the minimum number of dice moves needed to reach the final destination — the last square of the board.
I had never thought about completing the game using the minimum number of dice rolls, but in reality, that's exactly how you win — by reaching the end in the fewest moves possible! 😄
At first, I thought of solving it using the traditional index-based BFS, treating the board as a 2D matrix. But that felt a bit complicated to manage with all the zigzag indexing.
So I switched to a value-based approach, treating the board as a 1D array from 1 to n*n.
First, I mapped each value to its corresponding (i, j) position: val -> {i, j}
Then I applied BFS, keeping track of moves and handling the snakes and ladders accordingly.
Really, it was a fun problem — do try it out if you haven’t already! 🎲🐍🪜
Here is my code btw :
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
queue<int> q;
unordered_map<int, vector<int>> m;
int val = 1;
bool order = true; // true for left to right
for (int i = n - 1; i >= 0; i--) {
if (order) {
for (int j = 0; j < n; j++) {
m[val] = {i, j};
val++;
}
} else {
for (int j = n - 1; j >= 0; j--) {
m[val] = {i, j};
val++;
}
}
order = !order;
}
q.push(1);
unordered_map<int, bool> vis;
vis[1] = true;
int ans = 0;
while (!q.empty()) {
int size = q.size();
while (size--) {
int curr = q.front(); q.pop();
if (curr == n * n) return ans;
int next = min(curr + 6, n * n);
for (int i = curr + 1; i <= next; i++) {
int r = m[i][0];
int c = m[i][1];
int next = (board[r][c] != -1) ? board[r][c] : i;
if (!vis[next]) {
vis[next] = true;
q.push(next);
}
}
}
ans++;
}
return -1;
}
};