algoadvance

Leetcode 909. Snakes and Ladders

Problem Statement

You are given an n x n integer matrix board where the cells are labeled from 1 to n^2 in a Boustrophedon (or snake-like) way starting from board[n - 1][0] and ending at board[0][n - 1]. The board also contains ladders and snakes as follows:

You start from cell 1 and want to reach the cell n^2 in the least number of moves. Each move, you can roll a die with numbers 1 to 6, and move the appropriate number of steps forward (i.e., move from cell x to x + roll). If you reach a cell with a ladder or snake, you must move to the destination of that ladder or snake.

Return the least number of moves required to reach the square n^2. If it is not possible to reach the square, return -1.

Clarifying Questions

  1. Input Size: What are the constraints on the size of n?
    • The size n can range from 1 to 20.
  2. Nature of Inputs: Can the board contain invalid positions for ladders/snakes (negative values beyond -1)?
    • No, the board contains only -1 or valid cell numbers for ladders and snakes.
  3. Behavior of Dice Rolls: Is a single roll considered one move regardless of the die’s result?
    • Yes, each die roll is considered as one move regardless of the number on the die.
  4. Starting Point Confirmation: Do we always start from cell 1?
    • Yes, the starting point is always cell 1.
  5. Destination Confirmation: Do we always need to reach cell n^2 or return -1 if unreachable?
    • Yes, the goal is always to reach cell n^2.

Strategy

To solve this problem, we can use a Breadth-First Search (BFS) algorithm since BFS is optimal for finding the shortest path in an unweighted graph.

Steps:

  1. Initialize a queue for BFS and a boolean array to track visited cells.
  2. Start from cell 1, marking it as visited and enqueue it with 0 moves.
  3. For each cell, simulate the dice rolls (1 to 6) to compute the next cells.
  4. Adjust the resulting cell based on the ladders or snakes.
  5. If the resulting cell is the destination (n^2), return the number of moves.
  6. If not, mark it as visited and enqueue it.
  7. If the BFS completes without finding the destination, return -1.

Code

Below is the Java implementation of the above strategy:

import java.util.*;

public class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int target = n * n;
        boolean[] visited = new boolean[target + 1];
        Queue<int[]> queue = new LinkedList<>();
        
        queue.offer(new int[]{1, 0}); // {current cell, move count}
        visited[1] = true;
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cell = cur[0];
            int moves = cur[1];
            
            for (int i = 1; i <= 6; i++) {
                int next = cell + i;
                if (next > target) continue;
                
                int[] pos = getBoardPosition(next, n);
                int row = pos[0], col = pos[1];
                
                if (board[row][col] != -1) {
                    next = board[row][col];
                }
                
                if (next == target) {
                    return moves + 1;
                }
                
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(new int[]{next, moves + 1});
                }
            }
        }
        
        return -1;
    }
    
    // Helper function to convert cell number to board's (row, col)
    private int[] getBoardPosition(int num, int n) {
        int r = (num - 1) / n;
        int c = (num - 1) % n;
        if (r % 2 == 1) c = n - 1 - c;
        return new int[]{n - 1 - r, c};
    }
}

Time Complexity

The time complexity is O(n^2) because each cell is processed at most once, and there are at most n^2 cells on the board.

Space Complexity

The space complexity is also O(n^2) due to the queue and visited array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI