leetcode752. 打开转盘锁

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

我们可以将 0000 到 9999 这 10000 状态看成图上的 10000 个节点，两个节点之间存在一条边，当且仅当这两个节点对应的状态只有 1 位不同，且不同的那位相差 1（包括 0 和 9 也相差 1 的情况），并且这两个节点均不在数组 deadends 中。那么最终的答案即为 0000 到 target 的最短路径。

我们用广度优先搜索来找到最短路径，从 0000 开始搜索。对于每一个状态，它可以扩展到最多 8 个状态，即将它的第 i = 0, 1, 2, 3 位增加 1 或减少 1，将这些状态中没有搜索过并且不在 deadends 中的状态全部加入到队列中，并继续进行搜索。注意 0000 本身有可能也在 deadends 中。

破解密码的问题就像是一个树搜索的问题，把每一种一步变换的结果都放在该初状态的子节点里
（用deadends和visited进行剪枝，deadends用于去掉包含死路的解法，visited用于避免已经走过的路）
然后再去搜索这个target，搜索的深度就是最短的步数
可以用BFS来实现

class Solution {

public:

    int openLock(vector<string>& deadends, string target) {

        int step=;

        unordered_set<string> deadset(deadends.begin(),deadends.end());

        queue<string>tree;

        tree.push("");

        unordered_set<string> visited;

        visited.insert("");

        if(deadset.find("")!=deadset.end()) return -;

        while(!tree.empty())

        {

            int n=tree.size();

            for(int i=;i<n;i++)

            {

                string cur=tree.front();

                tree.pop();

                if(cur==target)

                    return step;

                //位上加一

                for(int j=;j<;j++)

                {

                    stringstream ss;

                    int cur_num;

                    string candidate1=cur;

                    ss<<candidate1[j];

                    ss>>cur_num;

                    cur_num=(cur_num+)%;

                    ss.clear();//清空输入输出流

                    ss<<cur_num;

                    ss>>candidate1[j];

                    ss.clear();

                    if(deadset.find(candidate1)==deadset.end() && visited.find(candidate1)==visited.end())

                    {

                        tree.push(candidate1);

                        visited.insert(candidate1);

                    }

                }

                //位上减一

                for(int j=;j<;j++)

                {

                    stringstream ss_1;

                    int cur_num_1;

                    string candidate2=cur;

                    ss_1<<candidate2[j];

                    ss_1>>cur_num_1;

                    cur_num_1-=;

                    if(cur_num_1<)

                        cur_num_1+=;

                    ss_1.clear();

                    ss_1<<cur_num_1;

                    ss_1>>candidate2;

                    ss_1.clear();

                    if(deadset.find(candidate2)==deadset.end() && visited.find(candidate2)==visited.end())

                    {

                        tree.push(candidate2);

                        visited.insert(candidate2);

                    }

                }

            }

            step++;

        }

        return -;

    }

};