752. 打开转盘锁

求最小旋转次数。这里选择BFS广度优先遍历

class Solution {
public:
    //如果其中一个拨轮往上调-------一共四个拨轮
    string plusOne(string str,int i)//str是传入进来要改变的密码组合  i记录的是第几个拨轮要进行调整
    {
        //如果当前i拨轮的数字是9，那么往上拨一位，应该是0
        if (str[i] == '9')
        {
            str[i] = '0';
        }
        else 
        {
            //平常情况，密码往前拨一位，就直接加一
            str[i]++;
        }
        return str;
    }
    //拨轮下拨
    string downOne(string str, int i)
    {
        str[i] = str[i] == '0' ? '9' : str[i]-1;
        return str;
    }
    int openLock(vector<string>& deadends, string target) 
    {
        //将所有死亡密码组合放入 unordered_set容器中，方便查看开锁的时候是否遇到了死亡密码
        //因为unordered_set容器底层实现是哈希表，有一个count函数用来统计容器中是键值为key的元素的个数
        unordered_set<string> deadset(deadends.begin(), deadends.end());
        //记录走过的密码
        unordered_set<string> visited;
        //当前初始密码入队，作为遍历起点
        queue<string> q;
        q.push("0000");
        //设置初始密码为走过的密码
        visited.insert("0000");
        //记录拨动的最小次数
        int step = 0;
        while (!q.empty())
        {
            int size = q.size();//当前这一批次，广度优先遍历，一批(一层)一批的走
            for (int i = 0; i < size; i++)
            {
                //取出队头元素
                string cur = q.front();
                q.pop();
                //判断当前取出的密码组合是不是死亡密码
                if (deadset.count(cur))//如果个数不为0，表示属于死亡密码的一种
                {
                    continue;//下面代码不再执行，直接再取出当前批次的下一个密码组合，进行判断
                }
                //如果是正确开锁密码，那么就返回拨动的最小次数
                if (cur == target)
                    return step;

                //当前批次的每一个密码组合都是四位数，每一个位数字都有上下拨动的两种可能
                //因此对于当前批次的每一个密码组合来说，每次转动会产生4*2=8种可能组合

                for (int i = 0; i < 4; i++)//i从0到3对应当前四位密码组合每一位密码
                {
                    //将当前密码组合的第i位数字上下改变产生的两种组合放入队列

                    string up = plusOne(cur, i);//上拨
                    //并且入队前，要查看上拨后的密码组合是否之前已经访问过
                    if (!visited.count(up))//没有访问过，就入队
                    {
                        q.push(up);  //放入当前密码(下一批次计算)
                        visited.insert(up); //放入走过密码
                    }

                    string down = downOne(cur, i);//下拨
                    if (!visited.count(down))
                    {
                        q.push(down);  //放入当前密码(下一批次计算)
                        visited.insert(down); //放入走过密码
                    }
                }
            }
            //当前批次密码组合全过了一遍之后,step++
            //因为这里求的是最少拨动次数，当前批次中某个密码组合与开锁密码相符，此时其余密码组合还未找到正确开锁密码，此时steo的值就是最少拨动次数
            step++;//波轮拨动一次
        }
        return -1;//无法解锁
    }
};