# [LeetCode 752. Open the Lock ](https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/603/week-1-june-1st-june-7th/3767/)
### Daily challenge Jun 4, 2021 (MEDIAN)

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

:::info
**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".
:::

:::info
**Example 2:**
Input:** deadends = ["8888"], target = "0009"
**Output:** 1
**Explanation:** We can turn the last wheel in reverse to move from "0000" -> "0009".
:::

:::info
**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.
:::

:::info
**Example 4:**
**Input:** deadends = ["0000"], target = "8888"
**Output:** -1
:::

:::warning
**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 1 : BFS :bulb: + :book:
**`164 ms ( 78.11% )`** **`O()`**

* 使用兩個 **`unordered_map`** 分別記錄 `走過的點`、`deadends`，**`step`** 紀錄當前步數。
* 使用 **`queue`** 實作 **`BFS`** 從 `"0000"` 當作起點，而每個點皆可產生其他 `八種` 可能 ( 每個 wheel 皆可`向上` or `向下`轉動 )。
* 若`重複經過` or `走到 deadends` 則跳過該種可能。
* 當 `queue` 為空時 ---> 表示 `impossible`，回傳 `-1`。
* 當走到 `target` 時 ---> 找到答案，回傳 `step`。

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_map<string, bool> used;
        unordered_map<string, bool> dead;
        queue<string> bfs;
        int step = 0;
        
        bfs.push("0000");
        used["0000"] = true;
        
        for(int i=0; i<deadends.size(); i++){
            dead[deadends[i]] = true;
        }
        
        while(!bfs.empty()){       
            int size = bfs.size();
            for(int i=0; i<size; i++){
                string temp = bfs.front();
                bfs.pop();

                if(temp == target)  return step;
                else if(dead.find(temp) != dead.end())  continue;
                else{
                    for(int j=0; j<4; j++){
                        string up = temp;
                        string down = temp;
                        
                        up[j] = (temp[j] - '0' + 1)%10 + '0';
                        down[j] = (temp[j] - '0' - 1 + 10)%10 + '0';
  
                        if(used.find(up) == used.end()){
                            bfs.push(up);
                            used[up] = true;
                        }
                        if(used.find(down) == used.end()){
                            bfs.push(down);
                            used[down] = true;
                        }
                    }
                }
            }
               
            step++;
        }
        
        return -1;
    }
};