Last Updated: 5 Sep, 2021

Modified Ludo

Moderate

Asked in companies

Solve now

Problem statement

You are given a board of‘ ‘N’ size. You can roll a dice and jump from position ‘i’ to i + 1, i + 2, i + 3, i + 4, i + 5, and i + 6 respectively. An array ‘connections’ of size ‘M’ is also provided where you can visit from the point ‘connections[i][0]’ to ‘connections[i][1]’ directly. Your task is to find the minimum number of dice rolls to reach from 1 to ‘N’ on the board.

For example:

Consider 'N' = 10, 'connections' = [[2, 10]]

We can go from 1 -> 2 with the help of dice (the number of operations increases by 1).
We can go from 2 -> 10 as 2 is directly connected to 10. No operation is required for this.
Hence the answer is 1.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the size of the board.

The second line contains a single integer ‘M’ denoting the size of the array ‘connections’.

Each of the next ‘M’ lines contains two space-separated integers representing the elements of the array ‘connections’.

Output Format:

For each test case, print a single integer representing the minimum number of dice rolls to reach from 1 to ‘N’ on the board.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10 ^ 6
1 <= M <= 10 ^ 6
1 <= connections[i][0], connections[i][1] <= N 

Time limit: 1 sec

Solve now

Approaches

01 Approach

We will call recursion to solve this problem.

Initially, we are at a distance 1. From here, we can either move to

1->2
1->3
1->4
1->5
1->6

Using our Dice.

If any connection of 1 is present in the array connections, then we can move from

connections[i][0] -> connections[i][1]

So we can move in any of the above-specified directions, and then we will call recursion for the rest part. I am maintaining a dynamic array ‘dp’ to store the solution.

Algorithm:

Initially, we will run a loop from start to start + 6, specifying the distance we can travel from the start using dice. If we are using dice, we will add 1 to our operations.

1->2
1->3
1->4
1->5
1->6
Next, we check whether we can take help of our connections,
connections[i][0] -> connections[i][1]
If we use ‘connections’ to traverse from one point to another, then we don't have to add 1 to our answer.
After each move, we will call recursion and store its answer in the ‘result’ variable.
We will store the answer to the recursive calls in a dp array.
The minimum of all the answers is going to be our final answer.

Solve now

02 Approach

We will maintain a queue and store all the points we can reach from the start. We will also maintain a distance array, storing the minimum distance to reach each index. For example, dice can show numbers from 1 to 6. If we start from 1, then distance[1] = 0 (since we are already at 1) and from there we can reach 2,3,4,5,6,7. So we will update their distance as

distance[2] = distance[1] + 1
distance[3] = distance[1] + 1
distance[4] = distance[1] + 1
distance[5] = distance[1] + 1
distance[6] = distance[1] + 1
distance[7] = distance[1] + 1

If there is a connection between 1 to any other number ‘x’ then we will update

distance[x] = distance[1]

We will add these numbers to our queue. Now we will see if we can reach any other number from the front of our queue through arr. If we are able to reach any other number through arr then we will update our distance array.

Algorithm:

Maintain a queue, and push the starting position that is 1 in it.
While the queue is not empty :
- Push all the possible points reachable from the front of the queue, and update the distance array.
- Check if through any connections we can find a shorter distance between the two points.
  - If yes, then we will update our distance array.

Solve now