# 752-Open the Lock
###### tags: `Medium`
* Question:
https://leetcode.com/problems/open-the-lock/

* Key:
1. 先確認deadends中有無"0000"，並把deadend都放入visited中，未來就可以同時檢查有嘗試過的數和deadends的數
2. 四位數遍尋跟其他地圖四個方位遍尋一樣，queue用來記錄下一次要嘗試的數字，每次嘗試就是檢查是否符合target，並對每個嘗試的數的每一位進行加一或減一(reverse wheel)，接著作檢查，放入queue和visited中，直到queue沒數值就停止遍尋，代表能找的範圍已經找完，沒找到代表碰到deadends

## BFS Solution

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        // Prepare for BFS
        // 因為不能走到 deadends 裡面的排列，所以我們直接放進 visited，這樣做 BFS 時就不會考慮這些路線
        unordered_set<string> visited(deadends.begin(), deadends.end());
        array<char, 10> digit= {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

        queue<string> todo;
        // 假設 0000 沒有在 visited(也就是 deadends 裡沒有) 中，我們才需要開始尋找
        if(!visited.count("0000")) {
            todo.push("0000");
            visited.insert("0000");
        }

        // Start BFS
        int steps = -1;
        while(!todo.empty()) {
            ++steps;
//queue有幾個數就對幾個數進行加或減一
            for(int sz = todo.size() - 1; sz >= 0; --sz) {
                string cur = todo.front();
                todo.pop();

                // Check if it's target
                if(cur == target) {
                    return steps;
                }

                // Go through neighbors
                // 如何找到對的 neighbor, i是為了遍尋4位數的哪一位數，j是為了對該位數增加+1或-1
                for(int i = 0; i < 4; ++i) {
                    for(int j = -1; j <= 1; j += 2) {
                        string neighbor = cur;
                        // Wrap around index to prevent out-of-bound error
                        neighbor[i] = digit[(neighbor[i]-'0'+j+10) % 10];
//遍尋過的數字就丟入queue跟visited
                        if(!visited.count(neighbor)) {
                            todo.push(neighbor);
                            visited.insert(neighbor);
                        }
                    }
                }
            }
        }

        return -1;
    }
};