Open the Lock

Problem Statement

Imagine a security mechanism with a combination lock consisting of four circular wheels, each labeled with digits from '0' to '9'. These wheels can rotate freely in both directions, allowing each digit to wrap around from '9' back to '0', and vice versa. Each single move involves turning one wheel by one slot.

The challenge begins with the lock set to '0000', and you're tasked with manipulating it to reach a designated "unlock" combination, referred to as the target. However, there is a twist: certain combinations termed as deadends immediately disable the lock if reached, making further movement impossible.

Your objective is to determine the minimal number of moves required to transform the initial state '0000' to the target combination without hitting any deadends along the way. If reaching the target is unfeasible due to these restrictions, the function should return -1.

Examples

Example 1

Input:

deadends = ["0201","0101","0102","1212","2002"], target = "0202"

Output:

6

Explanation:

A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2

Input:

deadends = ["8888"], target = "0009"

Output:

1

Explanation:

We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3

Input:

deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"

Output:

-1

Explanation:

We cannot reach the target without getting stuck.

Constraints

• 1 <= deadends.length <= 500
• deadends[i].length == 4
• target.length == 4
• target will not be in the list deadends.
• target and deadends[i] consist of digits only.

Approach and Intuition

The problem can be visualized as a shortest path search within an unweighted graph, where each node represents a possible state of the lock (i.e., a four-digit combination) and each edge corresponds to a single move or transition between states. The solution to navigating this space efficiently leans towards Breadth-First Search (BFS), a classic technique for finding shortest paths in such scenarios.

Key Steps in the Approach:

1. Initial Setup: Begin by marking all deadends as visited to prevent their inclusion in the search path.
2. Queue Initialization: Start the BFS with the queue initialized to the starting point '0000', provided it's not a deadend.
3. State Exploration: For each state, explore all potential states that can be reached by turning any of the four wheels one slot to the left or right.
4. Avoid Revisits: Maintain a set of visited states to avoid cycles or revisiting the same state, which would otherwise lead to inefficiencies and potential infinite loops.
5. Check for Target: At each step, check whether the target state is reached. If so, return the number of moves made.
6. Termination: If the queue gets exhausted without finding the target, return -1, indicating the target is unachievable from the given starting point without hitting a deadend.

Handling Edge Cases:

• If '0000' itself is a deadend, immediate recognition of this scenario is essential to return -1 outright, as no moves can be made.
• It's critical to efficiently manage transitions between states, ensuring that each possible move adheres to the wrap-around behavior of the wheels.

By adhering to this structured approach, the solution not only achieves the goal of finding the minimum number of moves (or determining impossibility) but does so in an optimal manner respecting the problem's constraints and conditions.

Solutions

class Solution {
public:
    int unlockSafe(vector<string>& blocklist, string goal) {
        unordered_map<char, char> nextDigit = {
            {'0', '1'}, 
            {'1', '2'}, 
            {'2', '3'}, 
            {'3', '4'}, 
            {'4', '5'},
            {'5', '6'}, 
            {'6', '7'}, 
            {'7', '8'}, 
            {'8', '9'}, 
            {'9', '0'}
        };
        unordered_map<char, char> prevDigit = {
            {'0', '9'}, 
            {'1', '0'}, 
            {'2', '1'}, 
            {'3', '2'}, 
            {'4', '3'},
            {'5', '4'}, 
            {'6', '5'}, 
            {'7', '6'}, 
            {'8', '7'}, 
            {'9', '8'}
        };
    
        unordered_set<string> blockedConfigs(blocklist.begin(), blocklist.end());
        queue<string> dropsQueue;
    
        int minSteps = 0;
    
        if (blockedConfigs.find("0000") != blockedConfigs.end()) {
            return -1;
        }
    
        dropsQueue.push("0000");
        blockedConfigs.insert("0000");
    
        while (!dropsQueue.empty()) {
            for (int size = dropsQueue.size(); size > 0; --size) {
                string currentConfig = dropsQueue.front();
                dropsQueue.pop();
    
                if (currentConfig == goal) {
                    return minSteps;
                }
    
                for (int wheel = 0; wheel < 4; ++wheel) {
                    string newConfig = currentConfig;
                    newConfig[wheel] = nextDigit[newConfig[wheel]];
                    if (blockedConfigs.find(newConfig) == blockedConfigs.end()) {
                        dropsQueue.push(newConfig);
                        blockedConfigs.insert(newConfig);
                    }
    
                    newConfig = currentConfig;
                    newConfig[wheel] = prevDigit[newConfig[wheel]];
                    if (blockedConfigs.find(newConfig) == blockedConfigs.end()) {
                        dropsQueue.push(newConfig);
                        blockedConfigs.insert(newConfig);
                    }
                }
            }
            minSteps++;
        }
        return -1;
    }
};