每日一题 LCR 109. 打开转盘锁

LCR 109. 打开转盘锁

首先尝试深度优先，但是效果不行。还得是广度优先。

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> st; 
        for(auto s : deadends){
            st.insert(s);
        }

        if(st.find("0000") != st.end() ){
            return -1;
        }

        unordered_set<string> visited;
        queue<pair<string,int>> que;
        que.push({"0000",0});


        while(!que.empty()){
            auto t = que.front();
            que.pop();
            string stemp = t.first;
            int    step = t.second;
            if(stemp == target){
                return step;
            }
            for(int i=0;i<4;++i){
                auto partTemp = getNext(stemp,i);
                string nx0 = partTemp.first;
                string nx1 = partTemp.second;

                if(visited.find(nx0) == visited.end() && st.find(nx0) == st.end()){
                    que.push({nx0,step+1});
                    visited.insert(nx0);
                }
                if(visited.find(nx1) == visited.end() && st.find(nx1) == st.end()){
                    que.push({nx1,step+1});
                    visited.insert(nx1);
                }
            }
        }
        return -1;
    }

    pair<string,string> getNext(string s,int idx){
        string nx0 = s;
        string nx1 = s;
        nx0[idx] = nx0[idx] != '9' ? nx0[idx] + 1 : '0';
        nx1[idx] = nx1[idx] != '0' ? nx1[idx] - 1 : '9';
        return {nx0,nx1}; 
    }
};