# LeetCode –  Open the Lock
Date: 2019-06-23


# 题目：

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

# 解题：

     遍历每个数字的每一位，然后-1，+1， 超过10的数字取余， 通过res记录遍历的层数，如果找到target直接返回res， 如果查看是否已经遍历或者再deadlock中， 没有的话加入队列进行遍历。 

# 实现：

```
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deadlock(deadends.begin(), deadends.end());
        if (deadlock.count("0000")){
           return -1;
        }
        int res=0;
        unordered_set<string> visited{{"0000"}};
        queue<string> q {{"0000"}};
        while (!q.empty()){
            ++res;
            int len = q.size();
            for (int k=0; k<len; k++){
                auto t=q.front(); 
                q.pop();
                for (int i=0; i<t.size();++i){
                    for (int j= -1; j<=1 ; ++j){
                        if (j == 0) continue;
                        string str = t;
                        str[i] = ((t[i] - '0') +10+j)%10+'0';
                        if (str == target){
                            return res;
                        }
                        if (!visited.count(str) && !deadlock.count(str)) {
                            q.push(str);
                        }
                        visited.insert(str);
                    }

                }
            }
        }
        return -1;
    }
};
```