752.打开转盘锁

两天宇宙人

2020-02-16

😂代码实现

必须通过set来存储deadends和已经访问过的字符串，不然会超时。

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        if(contain(deadends, "0000"))
            return -1;
        set<string> mp;
        int tl = 0, c1 = 1, c2 = 0;
        queue<string> q;
        q.push("0000");
        mp.insert("0000");
        for(auto x:deadends)
            mp.insert(x);
        string s;
        char x;
        while(q.size()) {
            s = q.front();
            q.pop();
            c1--;
            // cout << s << endl;
            if(s == target)
                return tl;
            for(int i = 0; i < 4; ++i) {
                char x = s[i];
                s[i] =  change_number(x, true);
                // cout << s << " " ;
                if(!mp.count(s)) { 
                    q.push(s);
                    mp.insert(s);
                    c2++;
                }
                s[i] = change_number(x, false);
                // cout << s << endl;
                if(!mp.count(s)) { 
                    q.push(s);
                    mp.insert(s);
                    c2++;
                }
                s[i] = x;
            }
            if(c1 ==0) {
                c1 = c2;
                c2 = 0;
                tl++;
            }
        }
        return -1;
    }
    char change_number(const char& c, bool zf) 
    {
        char x = c;
        // cout << x << zf << endl;
        if(zf) 
            return x == '9' ? '0' : x + 1;
        else 
            return x == '0' ? '9' : x - 1;
    }
    bool contain(const vector<string>& ss, const string & s)
    {
        for(auto x : ss) {
            if(x == s)
                return true;
        }
        return false;
    }
};