# 752. Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: `'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'`. The wheels can rotate freely and wrap around: for example we can turn `'9'` to be `'0'`, or `'0'` to be `'9'`. Each move consists of turning one wheel one slot.

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

You are given a list of `deadends` dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a `target` representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

**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 can't reach the target without getting stuck.
```

**Example 4:**\


```
Input: deadends = ["0000"], target = "8888"
Output: -1
```

**Note:**\


1. The length of `deadends` will be in the range `[1, 500]`.
2. `target` will not be in the list `deadends`.
3. Every string in `deadends` and the string `target` will be a string of 4 digits from the 10,000 possibilities `'0000'` to `'9999'`.

```cpp
// BFS
int openLock(vector<string>& deadends, string target) { // time: O(10^4); space: O(10^4)
    unordered_set<string> dead_try(deadends.begin(), deadends.end());
    const string start = "0000";
    if (dead_try.count(start)) return -1;
    int res = 0;
    unordered_set<string> visited({start});
    queue<string> q({start});
    while (!q.empty()) {
        ++res;
        for (int k = q.size() - 1; k >= 0; --k) {
            string t = q.front(); q.pop();
            for (int d = 0; d < 4; ++d) {
                for (int change = -1; change <= 1; ++change) {
                    if (change == 0) continue;
                    string str = t;
                    str[d] = ((str[d] - '0') + 10 + change) % 10 + '0';
                    if (str == target) return res;
                    if (visited.count(str)) continue;
                    visited.insert(str);
                    if (!dead_try.count(str)) q.push(str);
                }
            }
        }
    }
    return -1;
}
```

```cpp
// BFS
int openLock(vector<string>& deadends, string target) { // time: O(10^4); space: O(10^4)
    unordered_set<string> dead_try(deadends.begin(), deadends.end());
    const string start = "0000";
    if (dead_try.count(start)) return -1;
    int res = 0;
    unordered_set<string> visited({start});
    queue<string> q({start});
    while (!q.empty()) {
        ++res;
        for (int k = q.size() - 1; k >= 0; --k) {
            string t = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                char c = t[i];
                string str1 = t.substr(0, i) + to_string(c == '9' ? 0 : (c - '0' + 1)) + t.substr(i + 1);
                string str2 = t.substr(0, i) + to_string(c == '0' ? 9 : (c - '0' - 1)) + t.substr(i + 1);
                if (str1 == target || str2 == target) return res;
                if (!visited.count(str1) && !dead_try.count(str1)) q.push(str1);
                if (!visited.count(str2) && !dead_try.count(str2)) q.push(str2);
                visited.insert(str1);
                visited.insert(str2);
            }
        }
    }
    return -1;
}
```

```cpp
// Two-Ends BFS
int openLock(vector<string>& deadends, string target) { // time: O(10^4); space: O(10^4)
    const string start = "0000";
    unordered_set<string> begin({start}), end({target}), dead_try(deadends.begin(), deadends.end()), tmp;
    int res = 0;
    while (!begin.empty() && !end.empty()) {
        tmp.clear();
        if (begin.size() > end.size()) swap(begin, end);
        for (const string& str : begin) {
            if (end.count(str)) return res;
            if (dead_try.count(str)) continue;
            dead_try.insert(str); // insert visited string
            for (int i = 0; i < 4; ++i) {
                char c = str[i];
                string str1 = str.substr(0, i) + to_string(c == '9' ? 0 : (c - '0' + 1)) + str.substr(i + 1); // +1
                string str2 = str.substr(0, i) + to_string(c == '0' ? 9 : (c - '0' - 1)) + str.substr(i + 1); // -1
                if (!dead_try.count(str1)) tmp.insert(str1);
                if (!dead_try.count(str2)) tmp.insert(str2);
            }
        }
        ++res;
        begin = tmp;
    }
    return -1;
}
```

```cpp
// Two-Ends BFS
int openLock(vector<string>& deadends, string target) { // time: O(10^4); space: O(10^4)
    const string start = "0000";
    unordered_set<string> dead_try(deadends.begin(), deadends.end()), visited1({start}), visited2({target});
    queue<string> q1({start}), q2({target});
    if (dead_try.count(start)) return -1;
    int res = 0;
    while (!q1.empty() && !q2.empty()) {
        if (q1.size() > q2.size()) {
            swap(q1, q2);
            swap(visited1, visited2);
        }
        for (int k = q1.size() - 1; k >= 0; --k) {
            string t = q1.front(); q1.pop();
            if (visited2.count(t)) return res;
            for (int i = 0; i < 4; ++i) {
                char ch = t[i];
                for (int j = -1; j <= 1; j += 2) {
                    t[i] = '0' + ((ch - '0' + j + 10) % 10);
                    if (dead_try.count(t) || visited1.count(t)) continue;
                    q1.push(t);
                    visited1.insert(t);
                }
                t[i] = ch;
            }
        }
        ++res;
    }
    return -1;
}
```
