 New update is available. Click here to update.

# Ninja’s Safe

Last Updated: 18 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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.