A combinasion lock consists of four circular dials, each with digits from '0' to '9'. Each dial can rotate freely, allowing transitions such as '9' to '0' or '0' to '9'. A single rotation changes exactly one digit on one dial. The lock starts at '0000'. A list of deadends contains strings that, if reached, permanently lock the lock. Given a target string, determine the minimum number of rotations to reach it without hitting any deadend. If impossible, return -1.

Example 1: Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6 Explanatoin: A valid sequence is "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".

Example 2: Input: deadends = ["8888"], target = "0009" Output: 1 Explanation: Rotate the last digit backward once: "0000" -> "0009".

Example 3: Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Explanation: No path exists to the target without encountering a deadend.

Constraints:

• 1 <= deadends.length <= 500
• Each deadend string has length 4
• target string has length 4
• target is not in deadends
• All strings consist only of digits

Breadth-First Search (BFS) is suitable for finding shortest path in this unweighted graph. Represent states as strings of four digits. Use a queue to explore states level by level, tracking visited states and deadends to avoid cycles and invalid moves.

Implementation details:

• Initialize with '0000'.
• For each state, generate neighbors by incrementing or decrementing each digit modulo 10.
• Skip states in deadends or already visited.
• Return the step count when target is found, or -1 if queue is exhausted.

#include <vector>
#include <string>
#include <unordered_set>
#include <queue>
using namespace std;

class LockSolver {
public:
    int minRotations(vector<string>& deadends, string target) {
        unordered_set<string> blocked(deadends.begin(), deadends.end());
        if (blocked.count("0000")) return -1;
        
        queue<string> q;
        q.push("0000");
        blocked.insert("0000");
        int steps = 0;
        
        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                string current = q.front();
                q.pop();
                if (current == target) return steps;
                
                for (int pos = 0; pos < 4; ++pos) {
                    for (int delta : {1, -1}) {
                        string neighbor = current;
                        char& digit = neighbor[pos];
                        int num = (digit - '0' + delta + 10) % 10;
                        digit = num + '0';
                        if (!blocked.count(neighbor)) {
                            blocked.insert(neighbor);
                            q.push(neighbor);
                        }
                    }
                }
            }
            ++steps;
        }
        return -1;
    }
};

Test cases:

#include <cassert>
int main() {
    LockSolver solver;
    vector<string> deadends1 = {"0201","0101","0102","1212","2002"};
    assert(solver.minRotations(deadends1, "0202") == 6);
    
    vector<string> deadends2 = {"8888"};
    assert(solver.minRotations(deadends2, "0009") == 1);
    
    vector<string> deadends3 = {"8887","8889","8878","8898","8788","8988","7888","9888"};
    assert(solver.minRotations(deadends3, "8888") == -1);
    
    vector<string> deadends4 = {"0000"};
    assert(solver.minRotations(deadends4, "8888") == -1);
    return 0;
}