LeetCode.752 打开转盘锁

题目描述

思路

每次只能操作一个锁盘转动一个数字，有4个锁，每个锁可以向上转或向下转，因此共有8中可能。⽐如说从 "0000" 开始， 转⼀次， 可以穷举出 "1000", "9000", "0100","0900"... 共 8 种密码。 然后， 再以这 8 种密码作为基础， 对每个密码再转⼀下， 穷举出所有可能......

基于以上思想，可以将全部结果构成一个八叉树，其中每一层标识操作一步后的全部可能，因此要求最少步数，就是求这个八叉树的最小深度，求树的深度最简单的方法就是BFS(广度优先搜索算法)。

好了，到这里整体的算法框架可以搭建出来，其次就是对于细节的处理：
1.何时返回：当旋转后的某个锁和密码相等时，直接返回此时八叉树的深度。
2.deadends如何处理：可以用一个数组记录deadends，每次旋转锁前先判断这个锁是否被记录在deadends数组中，如果存在就跳过本次操作。
3.如何防止走回头路：可以用另一个数组used记录已经验证过的数字组合，如果已经被验证过，则跳过。这种情况可以和2合并，用一个数组即可。

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> used;
        //将禁入加入到已进入列表
        used.insert(deadends.begin(), deadends.end()); 
        if(used.count("0000")) return -1;

        int step = 0;
        queue<string> myque;
        string curlock = "0000";
        myque.push(curlock);
        used.insert(curlock);

        while(!myque.empty())
        {
            int len = myque.size();

            for(int i = 0; i < len; i++)
            {
                curlock = myque.front();
                myque.pop();

                if(!used.count(curlock)) continue;
                if(curlock == target) return step;

                for(int pos = 0; pos < 4; pos++)
                {
                    string str1 = upNum(curlock, pos);
                    if(!used.count(str1))
                    {
                        myque.push(str1);
                        used.insert(str1);
                    }
                    string str2 = downNum(curlock, pos);
                    if(!used.count(str2))
                    {
                        myque.push(str2);
                        used.insert(str2);
                    }
                }
            }
            step++;
        }

        return -1;
    }


    string upNum(string inlock, int pos)
    {
        string mylock = inlock;
        if(mylock[pos] == '9')
            mylock[pos] = '0';
        else
            mylock[pos]++;

        return mylock;
    }

    string downNum(string inlock, int pos)
    {
        string mylock = inlock;
        if(mylock[pos] == '0')
            mylock[pos] = '9';
        else
            mylock[pos]--;

        return mylock;
    }
};