New update is available. Click here to update.

Last Updated: 18 Mar, 2021

Difficulty: Moderate

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

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

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

```
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
```

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

The idea here is to use the unordered set of the same size as the ‘blockages’ and use a queue to insert the strings which are not visited as well as are not present in the ‘blockages’. Also,instead of dealing with the string , change them into integers and then move forward towards the result.

- Declare an empty queue and an unordered set of size ‘blockages’ and the count as ‘0’.
- Insert initial state into the queue if it is not present in the ‘blockages’; otherwise, return -1.
- Run a loop until the queue is not empty. The front of the queue is the result or not; if yes, then return count-1.
- Note its size.
- Decrease the size of the queue by one at every iteration.
- Check if our current state is the required result if it returns the ‘count’.
- Otherwise, check if it is visited or not. If not, insert it; otherwise, continue.
- Now change the string into the integers and change the integers by one-one places to check the possibility of new unvisited codes and then push them into the queue and increase the count by one

- Finally, return the answer either it is the number of steps to reach the result or -1 if it is impossible to open the safe.

SIMILAR PROBLEMS

Stock Span

Posted: 16 Jun, 2022

Difficulty: Moderate

Hills and Soldier

Posted: 7 Jul, 2022

Difficulty: Moderate

Hills and Soldier

Posted: 7 Jul, 2022

Difficulty: Moderate

Next Greater Element II

Posted: 9 Sep, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Co-Prime

Posted: 14 Dec, 2022

Difficulty: Hard

Popular Interview Problems: