Snake and Ladder

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
27 upvotes
Asked in companies
OlaDunzoIntuit

Problem statement

You have been given a Snake and Ladder Board with 'N' rows and 'N' columns with the numbers written from 1 to (N*N) starting from the bottom left of the board, and alternating direction each row.

For example

For a (6 x 6) board, the numbers are written as follows:

6*6 Board

You start from square 1 of the board (which is always in the last row and first column). On each square say 'X', you can throw a dice which can have six outcomes and you have total control over the outcome of dice throw and you want to find out the minimum number of throws required to reach the last cell.
Some of the squares contain Snakes and Ladders, and these are possibilities of a throw at square 'X':
You choose a destination square 'S' with number 'X+1', 'X+2', 'X+3', 'X+4', 'X+5', or 'X+6', provided this number is <= N*N.
If 'S' has a snake or ladder, you move to the destination of that snake or ladder.  Otherwise, you move to S.
A board square on row 'i' and column 'j' has a "Snake or Ladder" if board[i][j] != -1. The destination of that snake or ladder is board[i][j].
Note : 
You can only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving - you have to ignore the snake or ladder present on that square.

For example, if the board is:
-1 1 -1
-1 -1 9
-1 4 -1
Let's say on the first move your destination square is 2  [at row 2, column 1], then you finish your first move at 4 [at row 1, column 2] because you do not continue moving to 9 [at row 0, column 0] by taking the ladder from 4.

A square can also have a Snake or Ladder which will end at the same cell.
For example, if the board is:
-1 3 -1
-1 5 -1
-1 -1 9
Here we can see Snake/Ladder on square 5 [at row 1, column 1] will end on the same square 5.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of each test case or query contains a single integer value, 'N' representing the 'rows' and 'columns' for the two-dimensional square matrix.

The Second line onwards, the next 'N' lines or rows represent the ith row values.

Each of the i-th row constitutes 'N' column values separated by a single space.
Note : 
'-1' denotes the square doesn't contain any Snake or Ladder.
Output format : 
The only line of output prints the minimum number of throws required to reach the last cell of the board. If it is impossible to reach the last cell of the board, then print -1.
Constraints : 
1 <= N <= 10 ^ 2
1 <= board[i][j] <= N*N or board[i][j] = -1

Where (NxN) is the size of the board.
Sample Input 1 :
3
-1 1 -1
-1 -1 9
-1 4 -1
Sample Output 1 :
1
 Explanation to Sample Input 1 :
In the beginning, you start at square 1 [at row 2, column 0]. The optimal path will be:
1. You decided to move to 4 [at row 1, column 2] and must take the ladder to square 9 [at row 0, column 0].
You finished at last cell of the board in 1 dice throw.
Sample Input 2 :
6
-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
Sample Output 2 :
4
 Explanation to Sample Input 2 :
In the beginning, you start at square 1 [at row 5, column 0]. The optimal path will be:
1. You decide to move to square 2 [at row 5, column 1] and must take the ladder to square 15 [at row 5, column 1].
2. You then decide to move to square 17 [at row 3, column 5] and must take the snake to square 13 [at row 3, column 0].
3. You then decide to move to square 14 [at row 5, column 1] and must take the ladder to square 35 [at row 0, column 1].
4. You then decide to move to square 36 [at row 5, column 1].
You finished at last cell of the board in 4 dice throw.
Hint

Try considering the given Snake and Ladder board as a directed graph with the number of vertices equal to the number of cells in the board. The problem reduces to finding the shortest path in a graph.

Approaches (1)
BFS

We will use Breadth-First Search to find the shortest path from cellNumber 1 to cellNumber N*N.

  1. We will maintain a queue of cellNumber where the front of the queue will always contain a cell which can be reached by minimum dice throw from starting cell (cellNumber = 1).
  2. Create a minDiceThrow array of size N*N initialise it with the maximum value (INT_MAX)
  3. Start with pushing cellNumber 1 and updating minDiceThrow[1] = 0, as no. of throw required to reach cell no. 1 is 0.
  4. Iterate till we reach the destination or our queue is empty.
  5. In each iteration, we pop the front cellNumber having the minimum Dice Throw and try to update cells which are reachable from that cell at the cost of 1 dice throw.
  6. The cels which can be reached at 1 dice throw are:
    1. cellNumber + 1
    2. cellNumber + 2
    3. cellNumber + 3
    4. cellNumber + 4
    5. cellNumber + 5
    6. cellNumber + 6
  7. Now, if these cells contain any Snake or Ladder than change the nextCell to the end of the Snake or Ladder.
  8. If the updating minDiceThrow[] value of nextCell is more than prior minDiceThrow[] value then we update the minDiceThrow Array and push the nextCellNumber in our queue.
  9. Finally if minDiceThrow[N*N] = maximum value (INT_MAX) then we can’t reach last cell of the board so return -1 else return minDiceThrow[N*N].
  10. Also, take care of going out of bounds i.e. cellNumber more than N*N.
  11. The logic for getting row number and column no. from cellNumber is based on extracting the rowNumber by dividing cellNumber  by N and for column no. taking mod of cellNumber  by N. Also take care of alternating direction according to rowNumber.
Time Complexity

O(N ^ 2), where 'N' is the number of rows and number of columns in the board.

 

At max, we can push and pop each cell in our queue moreover each push or pop operation takes O(1) time. There are total N*N cells so, the overall complexity will be O(N ^ 2).

Space Complexity

O(N ^ 2), where 'N' is the number of rows and number of columns in the board.

 

We are using a minDiceThrow array of size N*N to store the minimum no. of dice throw required to reach each cell so, Overall Space Complexity is O(N ^ 2).

Code Solution
(100% EXP penalty)
Snake and Ladder
Full screen
Console