796 · 开锁

你面前有一个有四个圆形轮子的锁。每个轮子有10个槽:‘0’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’,‘7’,‘8’,‘9’。轮子可以自由旋转并环绕:例如，我们可以把‘9’变成‘0’，或者‘0’变成‘9’。每个动作包括转动一个轮子一个槽。
锁最初是‘0000’开始的，这是一个表示四个轮子状态的字符串。
你被给了一个死锁的列表，意思是如果锁显示了这些代码中的任何一个，锁的轮子将停止转动，你将无法打开它。
给定一个表示将解锁锁的轮子的值的目标，返回打开锁所需要的最小总次数，如果不可能，则返回-1。

一起战拖呀！

微信加【jiuzhang0607】备注【战拖】即可进入官方刷题群，团战offer！

1.死锁的列表长度将在[1,500]范围内。
2.目标不在死锁列表中。
3.每一个字符串在死锁列表和目标字段将是一串4位数字有10000种可能性从'0000'到'9999'。

样例

样例 1:

给出死锁列表=[“0201”、“0101”、“0102”、“1212”、“2002”),目标= " 0202 "
返回 6

解释:
一系列有效的动作将是“0000”->“1000”->“1100”->“1200”->“1201”->“1202”->“0202”。
请注意，像“0000”->“0001”->“0002”->“0102”->“0202”的序列将是无效的，
因为锁的轮子在显示器变成了“0102”后卡住了。

样例 2:

给出死锁列表 = ["8888"]， 目标 = "0009"
返回 1

解释:
我们可以从“0000”->“0009”转到最后一个转轮。

char preNum(char x)
{
    return x == '0' ? '9' : x - 1;
}

char bakNum(char x)
{
    return x == '9' ? '0' : x + 1;
}

vector<string> getStr(string &str)
{
    vector<string>ret;
    for (int i = 0; i < 4; i++)
    {
        char c = str[i];
        str[i] = preNum(c);
        ret.push_back(str);
        str[i] = bakNum(c);
        ret.push_back(str);
        str[i] = c;
    }
    return ret;
}

int openLock(vector<string> &deadends, string &target) {
    // Write your code here

    if (target == "0000")
    {
        return -1;
    }

    set<string> deaSet;
    for (int i = 0; i < deadends.size(); i++)
    {
        if (deadends[i] == "0000")
        {
            return -1;
        }
        deaSet.insert(deadends[i]);
    }
    set<string> queueSet;
    set<string> tmpQueSet;
    set<string>visitedSet;
    queueSet.insert("0000");
    visitedSet.insert("0000");
    int step = 0;
    while (queueSet.size()>0)
    {
        step++;
        for (auto it : queueSet)
        {
            vector<string> retVec = getStr(it);
            for (auto itt : retVec)
            {
                if (visitedSet.count(itt) > 0 || deaSet.count(itt) >0 )
                {
                    continue;
                }
                if (itt == target)
                {
                    return step;
                }
                visitedSet.insert(itt);
                tmpQueSet.insert(itt);
            }
            
        }
        queueSet = tmpQueSet;
        tmpQueSet.clear();
    }
    return -1;
}