Update appNew update is available. Click here to update.

Ninja’s Safe

Last Updated: 18 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

After an accident, Ninja is suffering from transient amnesia. He wants to open his safe but has forgotten his password.

The safe’s lock has 4 circular wheels. Each wheel has 10 slots: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The wheels can rotate clockwise as well as anti-clockwise: for example, we can turn 9 to be 0, or 0 to be 9. Each move consists of turning one wheel in one slot.

The lock initially starts at 0000, a string representing the state of the 4 wheels.

Ninja is given a list of ‘blockages’ dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning, and Ninja would be unable to open it.

There would be a ‘result’ given representing the wheels' value that will unlock the lock, return the minimum total number of turns Ninja is required to open the lock, or -1 if it is impossible for him to open it.

Help Ninja to open his safe.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

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

The next line contains ‘N’ space-separated strings denoting the values of the ‘blockages’ array.

The third line contains a single string denoting the ‘result’ value.

Output Format :

For each test case, print a single line containing numbers of turns or -1 as per the condition.

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

Note :

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

Constraints :

1 <= T <= 5 
1 <= N <= 500
blockages[i].length ==  4
result.length ==  4
result will not be in the list blockages
result and blockages[i] consists of only digits from ‘0’ to ‘9’.

Time Limit: 1sec

Approach 1

  • Declare a queue and a hashmap ‘visited’ and the count as ‘0’.
  • Make all the strings of ‘visited’ as true.
  • Now check whether the initial state “0000” is visited or not, if not push it into the queue.
  • Run a loop until the queue is not empty.
    • Increase the count by 1.
    • Decrease the queue size by one each time.
    • Check whether the front of the queue is the result or not; if yes, then return count-1.
    • Otherwise, check whether the top[i] is 9 or 0, if it is 9 then decrement ‘top[i]’ by 1 i.e. do top[i]--, if it is 0, then change it to 9 and sidewise check for the visited strings if they are not visited push them into the queue (here ‘top[i]’ are the digits of the string present in the front of the queue).
    • ‘count-1’ would be our final answer if opening the safe is possible.
  • Otherwise, return -1.
Try Problem