###### tags: `LeetCode` `BFS` `Queue` `Medium`
# LeetCode #752 [Open the Lock](https://leetcode.com/problems/open-the-lock/)
### (Medium)

你有一個帶有四個圓形撥輪的轉盤鎖。每個撥輪都有10個數字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每個撥輪可以自由旋轉：例如把 '9' 變為 '0'，'0' 變為 '9' 。每次旋轉都只能旋轉一個撥輪的一位數字。

鎖的初始數字為 '0000' ，一個代表四個撥輪的數字的字符串。

列表 deadends 包含了數組死亡數字，一旦撥輪的數字和列表裡的任何一個元素相同，這個鎖將會被永久鎖定，無法再被旋轉。

字符串 target 代表可以解鎖的數字，你需要給出解鎖需要的最小旋轉次數，如果無論如何不能解鎖，返回 -1 。

---
首先, 若"0000"在deadends中, 則回傳-1。

使用BFS遍歷從"0000"開始的每一動情況, 並使用unordered_set<int> visited紀錄, 省去重複時間。每一數字鎖皆可往前或往後撥動一次(+1或-1)。

使用queue進行BFS, 當佇列中的數字組合等於目標數時, 回傳步數。

---

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        queue<string> q;
        int steps = 0;
        unordered_set<string> set_(deadends.begin(), deadends.end());
        unordered_set<string> visited;
        if(set_.count("0000"))return -1;
        string test(target);
        q.push("0000");
        int locksize=4;
        while(!q.empty()){
            for(int i = q.size();i>0;i--){
                string s = q.front();q.pop();
                if(s==target)return steps;
                for(int j=0;j<locksize;j++){
                    const char c = s[j];
                    s[j] = c=='9'?'0':c+1;
                    if(!set_.count(s)&&!visited.count(s)){
                        q.push(s);
                        visited.insert(s);
                    }
                    s[j] = c=='0'?'9':c-1;
                    if(!set_.count(s)&&!visited.count(s)){
                        q.push(s);
                        visited.insert(s);
                    }
                    s[j]=c;
                }
            }
            
            steps++;
        }
        return -1;
    }
};