1、思路

• 每个密码锁有4个环，每次可以将其中一个环往上下两个方向转动，那么每一个密码都有8种转换方式。可以把这些状态想象成一张图，能够通过一次转动就得到的状态之间有一条边相连；

• 把init放入队列q1中，通过getNeighbors方法取得它所有可能的下一个状态，其数量为 $8$ 。遍历这些状态，判断它们是否存在于dead或visited中，若存在，则表示这个状态是一个死锁或已经访问过了；

• 将所有符合条件的下一状态放入q2中，每次交换队列q1与q2都意味着距离初始状态init有steps步的状态都访问完毕，接下来将访问距离为steps + 1的状态，因此距离加1。

2、代码

class Solution {
public:
    void clear(queue<string>& q)
    {
        queue<string> empty;
        swap(q, empty);
    }

    vector<string> getNeighbors(string cur)     //取得相邻的8个状态
    {
        vector<string> neighbors;

        for (int i = 0; i < cur.length(); ++ i)
        {
            char old = cur[i];

            char newChar = cur[i] == '0' ? '9' : cur[i] - 1;
            cur[i] = newChar;
            neighbors.push_back(cur);
            cur[i] = old;

            newChar = cur[i] == '9' ? '0' : cur[i] + 1;
            cur[i] = newChar;
            neighbors.push_back(cur);
            cur[i] = old;
        }

        return neighbors;
    }

    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());
        unordered_set<string> visited;

        string init = "0000";
        if (dead.find(init) != dead.end() || dead.find(target) != dead.end())
        {
            return -1;                          //无法到达的情况
        }

        queue<string> q1, q2;
        int steps = 0;
        q1.push(init);
        visited.insert(init);

        while (!q1.empty())
        {
            string cur = q1.front();
            q1.pop();

            if (cur == target) return steps;

            vector<string> neighbors = getNeighbors(cur);
            for (string neighbor : neighbors)   //遍历8个相邻状态
            {
                if (dead.find(neighbor) == dead.end() && visited.find(neighbor) == visited.end())
                {
                    q2.push(neighbor);          //将符合条件的状态入队
                    visited.insert(neighbor);   //并设置为已访问
                }
            }

            //q1为空，表示距离init有steps步的状态全都访问完毕，接下来要访问steps + 1步的状态了
            if (q1.empty())
            {
                ++ steps;
                q1 = q2;
                clear(q2);
            }
        }

        return -1;
    }
};