909. Snakes and Ladders #1750
-
909. Snakes and Ladders Difficulty: Medium Topics: You are given an You start on square
A board square on row Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.
Return the least number of dice rolls required to reach the square Example 1:
Example 2:
Constraints:
|
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
We need to find the minimum number of dice rolls required to reach the last square (n²) in a Snakes and Ladders game. The board is labeled in a Boustrophedon style, meaning the labeling alternates direction each row starting from the bottom left. The solution involves simulating the game using Breadth-First Search (BFS) to explore all possible paths level by level, ensuring the shortest path is found efficiently. Approach
Let's implement this solution in PHP: 909. Snakes and Ladders <?php
/**
* @param Integer[][] $board
* @return Integer
*/
function snakesAndLadders($board) {
$n = count($board);
$total = $n * $n;
$visited = array_fill(1, $total, false);
$queue = new SplQueue();
$queue->enqueue([1, 0]);
$visited[1] = true;
while (!$queue->isEmpty()) {
list($curr, $moves) = $queue->dequeue();
if ($curr == $total) {
return $moves;
}
for ($i = 1; $i <= 6; $i++) {
$next = $curr + $i;
if ($next > $total) {
break;
}
$q = intval(($next - 1) / $n);
$r = $n - 1 - $q;
$rem = ($next - 1) % $n;
if ($q % 2 == 0) {
$c = $rem;
} else {
$c = $n - 1 - $rem;
}
if ($board[$r][$c] != -1) {
$next = $board[$r][$c];
}
if (!$visited[$next]) {
$visited[$next] = true;
$queue->enqueue([$next, $moves + 1]);
}
}
}
return -1;
}
// Example usage:
$board1 = [
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]
];
echo snakesAndLadders($board1); // Output: 4
$board2 = [
[-1, -1],
[-1, 3]
];
echo "\n" . snakesAndLadders($board2); // Output: 1
?> Explanation:
This approach efficiently explores all possible paths using BFS, ensuring the shortest path is found while handling the game's rules for snakes and ladders. The complexity is O(n²) as each square is processed at most once. |
Beta Was this translation helpful? Give feedback.
We need to find the minimum number of dice rolls required to reach the last square (n²) in a Snakes and Ladders game. The board is labeled in a Boustrophedon style, meaning the labeling alternates direction each row starting from the bottom left. The solution involves simulating the game using Breadth-First Search (BFS) to explore all possible paths level by level, ensuring the shortest path is found efficiently.
Approach
Problem Analysis: The game involves moving from square 1 to square n² on an n x n board. Each move consists of rolling a 6-sided die, moving to one of the next 6 squares (if available), and following any snake or ladder encountered. The challenge is to compute the leas…